Submission #6070

#	Time	Username	Problem	Language	Result	Execution time	Memory
6070		ainta	우호 조약 체결 (JOI14_friends)	C++98	100 / 100	172 ms	17544 KiB

friends

#include<stdio.h>
#include<algorithm>
#include<vector>
#define N_ 100010
using namespace std;
int n, m, C[N_], par[N_];
long long C2[N_];
vector<int>E[N_], F[N_];
bool v[N_];
int SCC[N_], ord[N_], cnt;
int find(int a)
{
	if(a==par[a])return a;
	return par[a] = find(par[a]);
}
void DFS(int a)
{
	v[a] = true;
	int i;
	for(i=0;i<E[a].size();i++){
		if(!v[E[a][i]]){
			DFS(E[a][i]);
		}
	}
	ord[++cnt] = a;
}
void DFS2(int a)
{
	int i;
	C[cnt]++;
	SCC[a] = cnt;
	for(i=0;i<F[a].size();i++){
		if(!SCC[F[a][i]]){
			DFS2(F[a][i]);
		}
	}
}
void Merge(int a, int b){
	int x = find(a), y = find(b);
	if(x != y){
		par[y] = x;
		C[x] += C[y];
		C2[x] = (long long)C[x]*(C[x]-1);
	}
}
int main()
{
	int i, j, a, b;
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d",&a,&b);
		E[a].push_back(b);
		F[b].push_back(a);
	}
	for(i=1;i<=n;i++){
		if(!v[i]){
			DFS(i);
		}
	}
	cnt = 0;
	for(i=n;i>=1;i--){
		if(!SCC[ord[i]]){
			cnt++;
			DFS2(ord[i]);
		}
	}
	for(i=1;i<=n;i++)F[i].clear();
	for(i=1;i<=n;i++){
		for(j=0;j<E[i].size();j++){
			if(SCC[i] != SCC[E[i][j]]){
				F[SCC[i]].push_back(SCC[E[i][j]]);
			}
			else{
				C2[SCC[i]]++;
			}
		}
	}
	for(i=1;i<=cnt;i++)par[i]=i;
	long long Res = 0;
	for(i=1;i<=cnt;i++){
		a=find(i);
		if(C[a] <C2[a])C2[a] = (long long)C[a]*(C[a]-1);
		for(j=0;j<F[i].size();j++){
			if(C[a] == 1 && j){
				Merge(F[i][j-1],F[i][j]);
			}
			if(C[a] == 1) Res++;
			if(C[a] != 1) Merge(i,F[i][j]);
		}
	}
	for(i=1;i<=cnt;i++){
		if(i == find(i)){
			Res += C2[i];
		}
	}
	printf("%lld\n",Res);
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65