JOI 春合宿 2014 Day2 - Making Friends is Fun

問題文 : 友だちをつくろう

解法 :
JAPLJ 先生のわかりやすいスライド (コチラ) のとおりに実装すれば良い. 考察の神.

コード :

#include <bits/stdc++.h>

#define MAX_N (100001)

using namespace std;

vector<int> G[MAX_N], uG[MAX_N];
int col[MAX_N], ct[MAX_N];
bool vis[MAX_N];

void dfs(int v, int num)
{
	col[v] = num;
	for (int i = 0; i < uG[v].size(); i++)
		if (!col[uG[v][i]]) dfs(uG[v][i], num);
}

void find(int v)
{
	ct[col[v]]++;
	vis[v] = true;
	
	for (int i = 0; i < G[v].size(); i++)
		if (!vis[G[v][i]]) find(G[v][i]);
}

int main()
{
	int N, M;
	
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < M; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		G[a].push_back(b);
		uG[a].push_back(b);
		uG[b].push_back(a);
	}
	
	int num = 1;
	for (int v = 1; v <= N; v++){
		if (!col[v]) dfs(v, num++);
	}
	
	for (int v = 1; v <= N; v++){
		if (!vis[v] && G[v].size() >= 2){
			for (int i = 0; i < G[v].size(); i++)
				if (!vis[G[v][i]]) find(G[v][i]);
		}
	}
	
	long long ans = 0;
	for (int v = 1; v <= N; v++) ans += (long long)ct[v] * (ct[v] - 1);
	
	for (int v = 1; v <= N; v++)
		for (int i = 0; i < G[v].size(); i++)
			if (!vis[v] || !vis[G[v][i]]) ans++;
	
	printf("%lld\n", ans);
	
	return (0);
}