P2746 [USACO5.3]校园网Network of Schools

标签：eee   min   namespace   iostream   names   school   head   lse   out   

Aimeeeeeeeeeeeeeeeeeeeeeeeeee

很简单的东西

就是用tarjan缩个点，然后对于这个新图，考虑入读和出度为1的点就行了

#include
#include
#include
#include
#include
using namespace std;
int n;
int x;
int head[10000],headd[10000];
stack s;
int dfn[10000],low[10000];
int num[10000];
int chu[10000];
struct b{
	int to;
	int ne;
}ed[5000010],edd[5000001];
int ru[10000];
int xx,yy;
int Aimee;
void add(int f,int to){
	Aimee++;
	ed[Aimee].ne=head[f];
	ed[Aimee].to=to;
	head[f]=Aimee;
	return ;
}
void addd(int f,int to){
	Aimee++;
	edd[Aimee].ne=headd[f];
	edd[Aimee].to=to;
	headd[f]=Aimee;
	return ;
}
int Ai;
int Aim;
void dfs(int now){
	dfn[now]=low[now]=++Ai;
	s.push(now);
	for(int i=head[now];i;i=ed[i].ne){
		int v=ed[i].to;
		if(!dfn[v]){
			dfs(v);
			low[now]=min(low[now],low[v]);
		}else{
			if(!num[v]){
				low[now]=min(low[now],dfn[v]);
			}
		}
	}
	if(low[now]==dfn[now]){
		Aim++;
		while(1){
			int tem=s.top();
			s.pop();
			num[tem]=Aim;
			if(tem==now)
			break;
		} 
	}
} 
int Archie; 
int Aimeee;
int main(){
	scanf("%d",&n);
	for(int i=1;i

P2746 [USACO5.3]校园网Network of Schools

标签：eee   min   namespace   iostream   names   school   head   lse   out   

原文地址：https://www.cnblogs.com/For-Miku/p/13933829.html