ZOJ 3630 —— Information
2151 단어 억지로 연통 하 다
제목: n 개의 점, m 개의 변 이 있 습 니 다. 한 점 을 삭제 한 후에 강 한 연결 분량 포인트 의 최대 치 를 얻 고 최대 포인트 의 최소 치 를 구 합 니 다.
주의: 포인트 = 1 시 0;
사고: 모든 점 을 삭제 점 으로 매 거 하여 매번 강 한 연결 분량 의 최대 치 를 구하 고 가장 작은 것 을 취한 다.
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 110;
const int maxm = 10000;
int n, m;
int DFN[maxn], Low[maxn], Stack[maxn];
bool Instack[maxn];
int Time, taj, top;
int head[maxn], edgenum;
struct Edge
{
int from, to, next;
}edge[maxm];
int cnt;
vector<int>bcc[maxn];
int Tarjan(int u, int k)
{
DFN[u] = Low[u] = ++Time;
Stack[top++] = u;
Instack[u] = true;
for(int i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(v == k) continue;
if(DFN[v] == -1)
{
Tarjan(v, k);
Low[u] = min(Low[u], Low[v]);
}
else if(Instack[v] && Low[u] > DFN[v])
Low[u] = DFN[v];
}
if(Low[u] == DFN[u])
{
cnt = 0;
taj++;
bcc[taj].clear();
while(1)
{
int now = Stack[--top];
cnt++;
Instack[now] = false;
bcc[taj].push_back(now);
if(now == u) break;
}
}
return cnt;
}
void add(int u, int v)
{
edge[edgenum].from = u;
edge[edgenum].to = v;
edge[edgenum].next = head[u];
head[u] = edgenum++;
}
void init()
{
memset(head, -1, sizeof head);
edgenum = 0;
}
void init_taj()
{
memset(DFN, -1, sizeof DFN);
memset(Instack, false, sizeof Instack);
Time = taj = top = 0;
}
int Find_max()
{
int maxx = -1;
for(int i = 1;i<=taj;i++)
maxx = max(maxx, (int)bcc[i].size());
return maxx;
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
init();
while(m--)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
int ans = inf;
for(int t = 0;t<n;t++)
{
init_taj();
for(int i = 0;i<n;i++)
{
if(i == t) continue;
if(DFN[i] == -1)
Tarjan(i, t);
}
int tmp = Find_max();
ans = min(ans, tmp);
}
if(ans == 1) ans = 0;
printf("%d
", ans);
}
return 0;
}