ZOJ 3630 Information 強連通

題意：n m表示n個節點，m條邊，下面m行a b 表示a-b點有一條有向邊

題目：給定有向圖，刪去一個點後，可以求出該圖中強連通分量中最大的點數

問：刪去某點後，最大點數 最小是多少

思路：枚舉刪點，強連通求最大分量

mark

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include<stack>

#define N 1000
#define INF64 1152921504606846976
#define INF32 2147483647
#define R(x) x<<1|1
#define L(x) x<<1
#define Mid(x,y) (x+y)>>1
#define ll int
using namespace std;
vector<int>G[N],Tarjan[N];//Tarjan存下所有的強連通，其大小用 tar記錄
stack<int>mystack;
int n,m,tar;

inline ll Max(ll a,ll b){return a>b?a:b;}
inline ll Min(ll a,ll b){return a<b?a:b;}

int DFN[N],Low[N],Time,del;//del表示當前刪除的點  小寫的time會redeclared
bool instack[N],vis[N];
void tarjan(int u){
	int v;
	DFN[u]=Low[u]=++Time;
	mystack.push(u);  instack[u]=true;
	vis[u]=true;
	for(int i=0;i<G[u].size();i++)//遍歷u的所有子節點
	{
		v=G[u][i];
		if(v==del)continue;//刪點操作
		if(!DFN[v])
		{
			tarjan(v);
			Low[u]=Min(Low[u],Low[v]);
		}
		else if(instack[v])
			Low[u]=Min(Low[u],DFN[v]);
	}
	if(DFN[u]==Low[u])
		do
		{
			v=mystack.top();	mystack.pop();  instack[v]=false;
			Tarjan[tar].push_back(v);
		}while(u!=v);
		tar++;
		if(u==del){tar--;Tarjan[tar].clear();}
}
void InitTar(){
	memset(DFN,0,sizeof(DFN));	memset(Low,0,sizeof(Low));
	memset(instack,0,sizeof(instack));
	while(!mystack.empty())mystack.pop();
	for(int i=0;i<n;i++)Tarjan[i].clear();
	tar=Time=0;
}
int Findmin(){
	int ans=0;
	for(int i=0;i<tar;i++)
		ans=Max(ans,Tarjan[i].size());
	if(ans<2)ans=0;
	return ans;
}
int main(){
	int i,j;
	while(~scanf("%d%d",&n,&m)){
		for(i=0;i<n;i++)G[i].clear();
		while(m--)
		{
			int u,v;	scanf("%d %d",&u,&v);
			G[u].push_back(v);
		}
		int minm=INF32;
		for(i=0;i<n;i++)//i表示刪去的點,注意不要把刪掉的那個點當成一個強連通
		{
			InitTar();
			del=i;
			memset(vis,0,sizeof(vis));
			for(j=0;j<n;j++)
				if(!vis[j] && j!=del)
					tarjan(j);

			minm=Min(minm,Findmin());	if(!minm)break;
		}
		printf("%d\n",minm);
	}
	return 0;
}
/*
6 11
0 1
1 2
2 3
3 4
4 0
2 0
3 1
3 0
4 1
2 5
5 3



3 6
0 1
1 0
1 2
2 1
0 2
2 0

ans:
0 
2
*/