LightOJ - 1291 Real Life Traffic (tarjan算法求强连通分量)

原题地址：点击打开链接

该题意为问你最小让加几条边使得删除任何一条边所有的顶点任然连通。

如果是不含环的图，使得所有的顶点度大于或等于2删除任何一条边其他的顶点任然连通，那么该题即转化为求连通分量的问题，

求出连通分量之后缩点，然后统计出缩点后顶点的度，使得所有的顶点度大于等于2即可。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
#include<string.h>
using namespace std;
vector<int>e[10010];
int low[10010],dfn[10010],time;   //time时间戳  low记录顶点能到达最早的时间戳 dfn记录顶点时间戳  
bool instack[10010];    //判断是否在栈内   
int count;              //强连通分量数   
int belong[10010];      // 记录顶点所属的强连通分量   
int in[10010];         //记录入度   
stack<int>st;  
int n;
void tarjan(int s,int father)  //无向图 
{  
    dfn[s]=low[s]=++time;  
    st.push(s);  
    instack[s]=true;  
    for(int i=0;i<e[s].size();i++)  
    {  
        int v=e[s][i];
		if(v==father)            //不使用之前用过的边 
			continue;  
        if(dfn[v]==-1)                 //如果未遍历过 
        {  
            tarjan(v,s);  
            low[s]=min(low[v],low[s]);      //s能达到的最小时间戳 
        }  
        else if(instack[v])                 
            low[s]=min(dfn[v],low[s]);  
    }      
    if(dfn[s]==low[s])         //一个强连通分量 
    {  
        int u;  
        count++;  
        do  
        {  
            u=st.top();  
            st.pop();  
            instack[u]=false;  
            belong[u]=count;  
        }while(u!=s);      
    }  
}  
int solve()
{
	time=0;
	count=0;
	memset(instack,false,sizeof(instack));
	memset(belong,-1,sizeof(belong));
	memset(dfn,-1,sizeof(dfn));
	memset(in,0,sizeof(in));
	int i,j,res=0;
	for(i=0;i<n;i++)
	{
		if(dfn[i]==-1)
			tarjan(i,-1);
	}
	if(count==1)
		return 0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<e[i].size();j++)
		{
			int v=e[i][j];
			if(belong[i]==belong[v])
				continue;
			in[belong[i]]++;                    //统计强缩点后顶点的度 
			in[belong[v]]++;
		}
	}
	for(i=1;i<=count;i++)                       //由于是无向图，每条边统计了2次所以除以2 
	{
		if(in[i]/2<2)
			res+=2-in[i]/2;
	}
	res=(res+1)/2;
	return res;
}
int k=0;
int main()
{
	int t;
	int i,m,u,v,res=0;
	scanf("%d",&t);
	while(t--)
	{
	
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
		  e[i].clear();
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		int res=solve();
		printf("Case %d: %d\n",++k,res);
	}
	return 0;
}
/*


3
4 3
1 2
2 3
2 0

3 3
1 2
2 0
0 1

6 7
0 1
2 0
2 1
2 3
3 4
3 5
4 5

ans  2  0  1
*/