인기 있 는 소 (Tarjan 템 플 릿)
5492 단어 템 플 릿 문제
http://blog.csdn.net/jeryjeryjery/article/details/52829142?locationNum=4&fps=1
제목: 소 한 마리 한 마리 의 소원 은 가장 인기 있 는 소 가 되 는 것 이다.지금 은 N 마리 의 소 가 있 습 니 다. M 대 정수 (A, B) 를 드 리 겠 습 니 다. 소 A 는 소 B 가 인기 가 있다 고 생각 합 니 다.이런 관 계 는 전달 적 인 것 으로 A 가 B 가 인기 가 있다 고 생각 하고 B 가 C 가 인기 가 있다 고 생각한다 면 우 A 도 우 C 가 인기 가 있다 고 생각한다.당신 의 임 무 는 소 몇 마리 가 모든 소 에 게 인기 가 있다 고 생각 하 는 지 구 하 는 것 입 니 다.
입력: 첫 줄 두 개 N, M.다음 M 줄, 줄 당 두 개의 숫자 A, B 는 A 가 B 가 인기 가 있다 고 생각 한 다 는 뜻 이다.
출력: 하나의 정 수 를 출력 합 니 다. 즉, 몇 마리 의 소 가 모든 소 에 게 인기 가 있다 고 생각 합 니까?이러한 조건 을 만족 시 키 지 않 으 면 '0' 을 출력 합 니 다.
EG: in: 3 3 1 2 2 1 2 3
out: 1
코드:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct hehe
{
int u,v,next;
}bian[100050];
int n,m;
int low[500050],dfn[500050];
int num[500050],head[500050],chudu[500050],belong[500050];
int zhan[500050];
int cnt=0,tj=0,top=0,tot=0;
bool fangwen[500050];
inline void jianbian(int U,int V)
{
tj++;
bian[tj].u=U;
bian[tj].v=V;
bian[tj].next=head[U];
head[U]=tj;
}
inline void soudian(int u)
{
low[u]=dfn[u]=++cnt;
zhan[++top]=u;
fangwen[u]=true;
for(int p=head[u];p!=-1;p=bian[p].next)
{
int v=bian[p].v;
if(!dfn[v])
{
soudian(v);
low[u]=min(low[u],low[v]);
}
else
if(fangwen[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
++tot;
int v=-1;
while(u!=v)
{
v=zhan[top--];
belong[v]=tot;
num[tot]++;
fangwen[v]=false;
}
}
}
int main()
{
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;++i)
{
int u,v;
cin>>u>>v;
jianbian(u,v);
}
for(int i=1;i<=n;++i)
if(!dfn[i])
soudian(i);
for(int i=1;i<=m;++i)
if(belong[bian[i].u]!=belong[bian[i].v])
chudu[belong[bian[i].u]]++;
int res=0,ans;
for(int i=1;i<=tot;++i)
if(chudu[i]==0)
{
res++;
ans=i;
}
if(res==1) cout<else cout<<0;
return 0;
}