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
*/