BZOJ 1051: [HAOI 2006] 인 기 있 는 소

설명 소 한 마리 의 소원 은 가장 인기 있 는 소 가 되 는 것 이다.지금 은 N 마리 의 소 가 있 습 니 다. M 대 정수 (A, B) 를 드 리 겠 습 니 다. 소 A 는 소 B 가 인기 가 있다 고 생각 합 니 다.이런 관 계 는 전달 적 인 것 으로 A 가 B 가 인기 가 있다 고 생각 하고 B 가 C 가 인기 가 있다 고 생각한다 면 우 A 도 우 C 가 인기 가 있다 고 생각한다.당신 의 임 무 는 소 몇 마리 가 모든 소 에 게 인기 가 있다 고 생각 하 는 지 구 하 는 것 입 니 다.Input 첫 줄 두 개 N, M.이 어 M 줄, 줄 당 두 개의 수 A, B 는 A 가 B 가 인기 가 있다 고 생각 한 다 는 뜻 이다.Sample Input 3 1 2 1 2 1 2 3 Sample Output 1 HINT 100% data N < = 10000, M < = 50000 Source
먼저 그림 을 만 들 고 관계 에 따라 연 결 됩 니 다 (A 는 B 가 인기 가 있다 고 생각 합 니 다 = A → B)."모든 소 에 게 환영 을 받 아야 한다" 는 조건 이 상당히 까다롭다. 그렇다면 어떤 상황 에서 최종 답 은 > 1 일 까?이런 상황 은 하나의 강 한 연결 분량 에 만 나타난다 (서로 에 게 인기 가 있다 고 생각한다) (물론 하나의 단독 결점 도 하나의 강 한 연결 분량 으로 볼 수 있다). 이 강 한 연결 분량 은 모든 노드 가 답 이다. 곰 곰 이 생각해 보면 최종 적 으로 답 을 구성 하 는 강 한 연 결 량 은 하나 밖 에 없다.그리고 강 한 연결 분량 중 한 마리 의 소 가 어떤 소 가 인기 가 있다 고 생각한다 면 이 강 한 연결 분량 의 모든 소 를 얻 을 수 있다.이 성질 을 이용 하면 우 리 는 강 한 연결 분량 의 알고리즘 에 의존 할 수 있다.메모: next 는 일부 버 전 컴 파일 러 에서 키 워드 를 사용 하여 CE 를 초래 할 수 있 습 니 다. next 배열 을 사용 할 때 조심해 야 합 니 다. 첫째, Tarjan 후 DFS 를 진행 하고 횟수 를 통계 합 니 다. 만약 에 어떤 강 한 연결 분량 이 다른 모든 강 한 연결 분량 에 접근 할 수 있다 면 그것 이 답 입 니 다.

#include
#include
#include
#include
using namespace std;
const int N=10010;
const int M=50010;
int n,m,co,index1,num,next1[M],point[N],to[M];
int dfn[N],low[N],t[N],stack[N],top,ans[N],ans1;//i           t[i],ans[i]   i          
bool vis[N],vis1[N],vis2[N],instack[N];int ans2[N];
void in(int &x)
{
    char t=getchar();int f=1;x=0;
    while((t<48)or(t>57)){if(t=='-')f=-1;t=getchar();}
    while((t>=48)and(t<=57)){x=x*10+t-48;t=getchar();}
    x*=f;
}
void add(int from,int to1)
{
    ++co;
    next1[co]=point[from];
    point[from]=co;
    to[co]=to1;
}
void tarjan(int u)
{
    vis[u]=instack[u]=1;
    stack[++top]=u;
    low[u]=dfn[u]=++index1;
    for (int now=point[u];now;now=next1[now])
    {
        int v=to[now];
        if (!vis[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
        if (instack[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u])
    {
        ++num;int v=0;
        while(v!=u)
        {
            v=stack[top--];
            t[v]=num;++ans[num];
            instack[v]=0;
        }
    }
}
void dfs(int now,int now1)
{
    vis[now]=1;
    if ((t[now]!=now1)and(!vis1[t[now]]))
    {++ans2[t[now]];vis1[t[now]]=1;}
    for (int i=point[now];i;i=next1[i])
    {
        int v=to[i];
        if (!vis[v]) dfs(v,now1);
    }
}
int main()
{
    in(n),in(m);
    for (int i=1;i<=m;++i)
    {
        int x,y;
        in(x),in(y);
        add(x,y);
    }
    for (int i=1;i<=n;++i)
    if (!vis[i]) tarjan(i);
    for (int i=1;i<=n;++i)
    if (!vis2[t[i]])
    {
        memset(vis,0,sizeof(vis));
        memset(vis1,0,sizeof(vis1));
        dfs(i,t[i]);vis2[t[i]]=1;
    }
    for (int i=1;i<=n;++i)
    if (ans2[t[i]]==(num-1))
    {ans1=ans[t[i]];break;}
    printf("%d",ans1);
    return 0;
}

방법 2: 강 한 연결 분량 을 이용 하여 점 을 줄 이 고 전체 강 한 연결 분량 을 하나의 결점 으로 보고 그림 의 연결 변 을 재 구축 하 며 출 도 를 0 으로 하 는 것 이 답 이다.주의: 어떤 강 한 연결 분량 이 고립 될 수 있 습 니 다 (입 도 출 도 0). 해결 방법 은 모든 강 한 연결 분량 을 한 번 훑 어 보 는 것 입 니 다. 만약 에 여러 개의 출 도 0 의 강 한 연결 분량 이 나타 나 면 0 을 출력 합 니 다.

#include
#include
#include
#include
using namespace std;
const int N=10010;
const int M=50010;
int n,m,co,co1,index1,num,next1[M],point[N],to[M];
int dfn[N],low[N],t[N],stack[N],top,ans[N],ans1;
bool vis[N],instack[N];int point2[N],next2[M],to2[M];
void in(int &x)
{
    char t=getchar();int f=1;x=0;
    while((t<48)or(t>57)){if(t=='-')f=-1;t=getchar();}
    while((t>=48)and(t<=57)){x=x*10+t-48;t=getchar();}
    x*=f;
}
void add(int from,int to1)
{
    ++co;
    next1[co]=point[from];
    point[from]=co;
    to[co]=to1;
}
void add1(int from,int to1)
{
    ++co1;
    next2[co1]=point2[from];
    point2[from]=co1;
    to2[co1]=to1;
}
void tarjan(int u)
{
    vis[u]=instack[u]=1;
    stack[++top]=u;
    low[u]=dfn[u]=++index1;
    for (int now=point[u];now;now=next1[now])
    {
        int v=to[now];
        if (!vis[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
        if (instack[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u])
    {
        ++num;int v=0;
        while(v!=u)
        {
            v=stack[top--];
            t[v]=num;++ans[num];
            instack[v]=0;
        }
    }
}
void work(int u)
{
    for (int i=point[u];i;i=next1[i])
    {
        int v=to[i];
        if (t[v]!=t[u]) add1(t[u],t[v]);
    }
}
int main()
{
    in(n),in(m);
    for (int i=1;i<=m;++i)
    {
        int x,y;
        in(x),in(y);
        add(x,y);
    }
    for (int i=1;i<=n;++i)
    if (!vis[i]) tarjan(i);
    for (int i=1;i<=n;++i) work(i);
    for (int i=1;i<=num;++i)
    if (!point2[i])
        if (ans1) {ans1=0;break;}
        else ans1=ans[i];
    printf("%d",ans1);
    return 0;
}