| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
小菜求DEBUG 先求强连通分量 在对每个连通分量中的点处理 如果有一个点的出度指向其他连通分量 则此连通分量中的点都不是SINK 思路不对么?#include<iostream>
#include<vector>
using namespace std;
const int N=5100;
class Graph
{
private:
vector<int> g[N];
int n,m,h[N],id[N],sign[N];
int cnt,scnt,dfn[N],low[N],cur[N],cur2[N];
int stack[N],top,est[N],etop;
void dfs(int);
void init();
public:
bool build();
void scR();
};
void Graph::init()
{
for(int i=0;i<=n+1;i++)
{
g[i].clear();
dfn[i]=-1;
h[i]=id[i]=sign[i]=low[i]=cur[i]=cur2[i]=0;
}
cnt=scnt=top=etop=0;
}
bool Graph::build()
{
if(scanf("%d",&n)==EOF)
return false;
if(n==0)
return false;
scanf("%d",&m);
init();
for(int i=0;i<m;i++)
{
int s,e;
scanf("%d%d",&s,&e);
s--,e--;
g[s].push_back(e);
}
}
void Graph::scR()
{
for(int i=0;i<n;i++)
cur2[i]=cur[i]=g[i].size()-1;
for(int i=0;i<n;i++) //非递归TARJAN求强连通分量
{
if(dfn[i]==-1)
dfs(i);
}
for(int i=0;i<n;i++) //如果连通分量中有点指向其他连通分量 则该连通分量中的点不是sink
{
for(int j=0;j<=cur2[i]&&sign[id[i]]==0;j++)
{
if(id[i]!=id[g[i][j]])
sign[id[i]]=1;
}
}
int k=0;
for(int i=0;i<n;i++)
{
if(sign[id[i]]==0)
{
if(k==0)
{
printf("%d",i+1);
k++;
}
else
printf(" %d",i+1);
}
}
printf("\n");
}
void Graph::dfs(int src)
{
top=etop=0;
stack[top]=src,top++;
while(top!=0)
{
int c=stack[top-1];
if(dfn[c]==-1)
h[c]=dfn[c]=low[c]=cnt,cnt++,est[etop]=c,etop++;
for(;cur[c]>=0;cur[c]--)
{
int no=g[c][cur[c]];
if(dfn[no]==-1)
{
stack[top]=no,top++;
break;
}
h[c]<?=low[no];
}
if(cur[c]>=0)
continue;
top--;
int k;
if(h[c]!=low[c])
{
low[c]=h[c];
continue;
}
do
{
etop--,k=est[etop];
id[k]=scnt,low[k]=N;
}while(k!=c);
scnt++;
}
}
int main()
{
//freopen("2039.in","r",stdin);
//freopen("test.out","w",stdout);
Graph graph;
while(graph.build())
graph.scR();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator