poj2186 tarjin+缩点

桃扇骨 2022-03-10 05:46 197阅读 0赞

题目大意：

每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这

种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头

牛被所有的牛认为是受欢迎的。

思路：求出所有联通块  ，再把所有联通块当作点  构成了一个有向无环图   然后找到出度为0 的那个联通块 输出它有多少点

如果出度为0 的联通块不止一个   那么这个图符合条件的点数为  0

贴代码：

#include<bits/stdc++.h>
    #include<vector>
    using namespace std;
    int in,n,m,a,b,sum,superpoint[10005],v[10005],low[10005],dfn[10005],chu[10005],ccnt[10005];
    vector<int> G[10005];
    stack<int> s;
    void tarjin(int x){
        v[x]=1;
        s.push(x);
        low[x]=dfn[x]=++in;
        for(int i=0;i<G[x].size();i++){
            if(!dfn[G[x][i]]){
                tarjin(G[x][i]);
                low[x]=min(low[x],low[G[x][i]]);
            }else if(v[G[x][i]]){
                low[x]=min(low[x],dfn[G[x][i]]);
            }
        }
        if(low[x]==dfn[x]){
            v[x]=0;
            sum++;
            while(s.top()!=x){
                v[s.top()]=0;
                superpoint[s.top()]=sum;//第几个超级点
                s.pop();
            }
            superpoint[x]=sum;
            s.pop();
        }
    }
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a>>b;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]){
                tarjin(i);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<G[i].size();j++){
                if(superpoint[i]!=superpoint[j])
                    chu[superpoint[i]++;
            }//记录每个联通块的出度
            ccnt[superpoint[i]]++;//记录每个超级点的数量
        }
        int ans=0,tem;
        for(int i=1;i<=sum;i++){
            if(chu[i]==0){
                ans+=ccnt[i];
                tem++;
            }
        }
        if(tem!=1)cout<<0;
        else cout<<ans;
        return 0;
    }

再来个强大注释版：

//求最后有几头cow被all cow 崇拜
    #include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5;
    vector<int> v[maxn];
    stack<int> s;
    int dfn[maxn],low[maxn],superpoint[maxn],vis[maxn],cnt=0,sum=0,chu[maxn],ccnt[maxn];
    //super doit 是连通块的根
    void tarjan(int a)
    {
    	vis[a]=1;
    	dfn[a]=low[a]=++cnt;
    	s.push(a);
    	for(int i=0;i<v[a].size();i++)
    	{
    		int e=v[a][i];
    		if(dfn[e]==0)
    		{
    			tarjan(e);
    			low[a]=min(low[a],low[e]);
    		}
    		else if(vis[e]==1)
    		{
    			low[a]=min(low[a],dfn[e]);
    		}
    	}
    	if(low[a]==dfn[a])
    	{
    		sum++; //记录这个联通块的序号
    		while(1)
    		{
    			int e=s.top();
    			vis[e]=0;
    			s.pop();
    			superpoint[e]=sum;  //记录该点属于哪个超级点
    			if(e==a)
    				break;
    		}
    	}
    }
    int main()
    {
    	int n,m;
    	cin>>n>>m;
    	while(m--)
    	{
    		int a,b;
    		scanf("%d %d",&a,&b);
    		v[a].push_back(b);
    	}//建立图中的头
    	tarjan(1);//杀掉废话代码
    	for(int i=1;i<=n;i++)
    	{
    		if(dfn[i]==0)
    			tarjan(i); //这步要记住！因为不一定所有都能由tanrjan(1)可达，有可能有几个点是孤立的小团体~
    	}
    	for(int i=1;i<=n;i++)//枚举所有点
    	{
    		for(int j=0;j<v[i].size();j++)
    		{
    			if(superpoint[i]!=superpoint[j])
    			{
    				chu[superpoint[i]]++;  //记录这个超级点的出度
    			}
    		}
    		ccnt[superpoint[i]]++;  //记录这个超级点涵盖了多少个单点
    	}//找到每个点的初度和数量
    	int temp=0;
    	int ans;
    	for(int i=1;i<=sum;i++)//对每个超级点进行拖布排序
    	{
    		if(chu[i]==0)
    		{
    			temp++;
    			ans=ccnt[i];//某个超级点
    		}
    	}//化为有向无环图
    	if(temp==0 || temp>1)
    		cout<<0;
    	else if(temp==1)
    		cout<<ans;  //如果只有一个超级点满足出度为0，则输出该超级点所涵盖的点的数量，为所求。
    	return 0;
    }