http://acm.timus.ru/problem.aspx?space=1&num=1198
英語(yǔ)真的是硬傷呀 讀了N遍 愣是沒有讀懂 最后看了別人的提示
反正是聯(lián)通分量 縮點(diǎn) 然后對(duì)縮點(diǎn)后的圖進(jìn)行求解 縮點(diǎn)后的圖必須有且僅有一個(gè)點(diǎn)入度為0
然后輸出這個(gè)入度為0的點(diǎn)所包含的所有原來的點(diǎn) （按順序）
注意輸入數(shù)據(jù)量很多 要用scanf 用cin 有可能超時(shí)
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#define LL long long
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int N=2005;
const int INF=0x3f3f3f3f;
//typedef pair<int,int>point;
int head[N],I;
struct node
{
int j,next;
}side[N*2000];
int dfn[N],low[N],f[N],deep;
bool visited[N],in[N];
int sum[N];
stack<int>st;
void add(int i,int j)
{
side[I].j=j;
side[I].next=head[i];
head[i]=I++;
}
void dfs(int x)
{
dfn[x]=low[x]=deep++;
st.push(x);
in[x]=true;
visited[x]=true;
for(int t=head[x];t!=-1;t=side[t].next)
{
int j=side[t].j;
if(!visited[j])
{
dfs(j);
low[x]=min(low[x],low[j]);
}else if(in[j])
{
low[x]=min(low[x],dfn[j]);
}
}
if(low[x]==dfn[x])
{
while(st.top()!=x)
{
in[st.top()]=false;
f[st.top()]=x;
st.pop();
}
in[st.top()]=false;
f[st.top()]=x;
st.pop();
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(head,-1,sizeof(head));
I=0;
for(int i=1;i<=n;++i)
{
int k;
while(scanf("%d",&k))
{
if(k==0) break;
add(i,k);
}
}
while(!st.empty())
st.pop();
memset(in,false,sizeof(in));
memset(visited ,false,sizeof(visited));
deep=1;
for(int i=1;i<=n;++i)
if(!visited[i])
dfs(i);
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;++i)
{
for(int t=head[i];t!=-1;t=side[t].next)
{
int j=side[t].j;
if(f[i]!=f[j])
++sum[f[j]];
}
}
vector<int>vt;
int flag=0;
for(int i=1;i<=n;++i)
if(sum[f[i]]==0)
{
vt.push_back(i);
if(flag==0)
flag=f[i];
else if(f[i]!=flag)
flag=-1;
}
if(flag>0)
{
sort(vt.begin(),vt.end());
for(unsigned int i=0;i<vt.size();++i)
cout<<vt[i]<<" ";
}
cout<<"0"<<endl;
}
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
