tarjan算法很犀利,不解释,不解释。。。
缩点然后判断度数
#include<iostream>
#include<vector>
#include<cstring>
#include<deque>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<algorithm>
#include<cassert>
#define pb push_back
using namespace std;
const int maxn = 111;
vector<int>g[maxn];
vector<int>v[maxn];
vector<int>s;
bool hash[maxn][maxn];
int be[maxn];
int dfn[maxn];
int low[maxn];
bool ins[maxn];
int n,df,nb;
int in[maxn];
int out[maxn];
int sa,sd;
void tarjan(int now)
{
low[now] = dfn[now] = df++;
s.pb(now);
ins[now] = true;
int to;
for(int i=0;i<g[now].size();i++)
{
to = g[now][i];
if(!dfn[to])
{
tarjan(to);
low[now] = min(low[to],low[now]);
}
else if( ins[to] )
{
low[now] = min(low[to],low[now]);
}
}
if(low[now] == dfn[now] )
{
while(s.back()!=now)
{
to = s.back();
be[to] = nb;
s.pop_back();
ins[to] = false;
}
be[now] = nb++;
ins[now] = false;
s.pop_back();
}
return ;
}
void start()
{
s.clear();
nb = df = 1;
memset(ins,false,sizeof(ins));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(be,0,sizeof(be));
memset(hash,false,sizeof(hash));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
/* for(int i=1;i<=n;i++)
{
cout<<"dfn["<<i<<"] == "<<dfn[i]<<endl;
cout<<"low["<<i<<"] == "<<low[i]<<endl;
cout<<"be["<<i<<"] == "<<be[i]<<endl;
} */
nb--;
if(nb==1)
{
sa = 1;
sd = 0;
return ;
}
int from,to;
for(int i=1;i<=n;i++)
{
from = be[i];
for(int j=0;j<g[i].size();j++)
{
to = be[g[i][j]];
if(from != to && !hash[from][to] )
{
hash[from][to] = true;
v[from].pb(to);
}
}
}
for(int i=1;i<=nb;i++)
{
from = i;
for(int j=0;j<v[i].size();j++)
{
to = v[i][j];
out[from]++;
in[to]++;
}
}
sa = 0;
sd = 0;
for(int i=1;i<=nb;i++)
{
if(!in[i])
{
sa++;
}
if(!out[i])
{
sd++;
}
}
sd = max(sa,sd);
return ;
}
int main()
{
while(cin>>n)
{
for(int i=1;i<=n;i++)
{
g[i].clear();
v[i].clear();
}
int x;
for(int i=1;i<=n;i++)
{
while(cin>>x)
{
if( !x )
{
break;
}
g[i].push_back(x);
}
}
start();
cout<<sa<<endl<<sd<<endl;
}
return 0;
}
分享到:
相关推荐
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ2531-Network Saboteur 解题报告+AC代码
poj 1459 Power Network.md
poj 2771 Guardian of Decency.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 2903 Joy of Mobile Routing.md
poj 3174 Alignment of the Planets.md
北大POJ1459-Power Network 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
利用并查集判断环路,以及快速排序计算最小生成树
北大POJ2109-Power of Cryptography 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2739-Sum of Consecutive Prime Numbers 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ2002-Squares 解题报告+AC代码