POJ2762 Going from u to v or from v to u?

Description：

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Analysis：

先用强连通缩点来化简图，然后在图上进行拓扑排序，如果排序过程中，出现1个以上的点入度同时为0时，那么就不满足条件。就是说，要满足从u到v，这个拓扑图应是一条链，否则不满足题意。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define M 500001
#define N 500001
using namespace std;
struct edge{
	int u,v,next;
}e[M],G[M];
int head[N],st[N],scc[N],dfn[N],low[N],size[N],in[N],top,num_dfs,num_scc,num_edge1,num_edge2,n,m,T;
inline void add(int u,int v,edge E[],int & num){
    E[++num].next = head[u];
    E[num].u = u;
    E[num].v = v;
    head[u] = num;
}
bool topologicalSort(){
	queue<int> Q;
	for(int i = 1;i <= num_scc;++i){
		if(!in[i]) Q.push(i);
	}
	if(Q.size() > 1) return 0;
	while(!Q.empty()){
		int u = Q.front();Q.pop();
		int cnt = 0;
		for(int i = head[u];i;i = G[i].next){
			int v = G[i].v;
			if(!(--in[v])) ++cnt,Q.push(v);
			if(cnt > 1) return 0;
		}
	}
	return 1;
}
void tarjan(int u){
	dfn[u] = low[u] = ++num_dfs;
	st[++top] = u;
	for(int i = head[u];i;i = e[i].next){
		int v = e[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}else{
			if(!scc[v])
				low[u] = min(low[u],dfn[v]);
		}
	}
	if(low[u] == dfn[u]){
		++num_scc;
		scc[u] = num_scc;
		++size[num_scc];
		while(st[top] != u){
			scc[st[top]] = num_scc;
			++size[num_scc];
			--top;
		}
		--top;
	}
}
void solve(){
	for(int i = 1;i <= n;++i){
		if(!dfn[i])
			tarjan(i);
	}
	memset(head,0,sizeof(head));
	for(int i = 1;i <= m;++i){
        if(scc[e[i].u ] != scc[e[i].v]){
            add(scc[e[i].u],scc[e[i].v],G,num_edge2);
            ++in[scc[e[i].v]];
        }
    }
	if(topologicalSort()){
		printf("Yes
");
	}
	else{
		printf("No
");
	}
}
inline void clear(){
	memset(e,0,sizeof(e));
	memset(head,0,sizeof(head));
	memset(scc,0,sizeof(scc));
	memset(dfn,0,sizeof(dfn));
	memset(in,0,sizeof(in));
	memset(low,0,sizeof(low));
	top = num_edge1 = num_edge2 = num_dfs = num_scc = 0;
}
int main(){
	scanf("%d",&T);
	while(T--){
		clear();
		scanf("%d %d",&n,&m);
		for(int i = 1;i <= m;++i){
			int a,b;
			scanf("%d %d",&a,&b);
			add(a,b,e,num_edge1);
		}
		solve();
	}
	return 0;
}

加强版： Luogu P2272[ZJOI2007]最大半连通子图