POJ 2553 강 연통 분량 Tarjan

비극 적 으로 문 제 를 잘못 읽 었 습 니 다.Popular Cow 와 마찬가지 로 모든 점 에 대해 서 는 이러한 점 을 sink 점 으로 할 수 있다 고 생각 했 습 니 다.실제 적 으로 모든 w 점 에서 v 점 까지 경로 가 있 고 v 에서 w 까지 경로 가 있다 는 점 을 sink 점 이 라 고 하기 때문에 w - > v 에 끝 이 있 고 v - > w 에 끝 이 없다 는 점 은 sink 점 이 아니다.상기 두 가지 조건 이 모두 만족 할 때 만 sink 점 입 니 다.
이 문제 에 대한 분석:
먼저 판단 하 는 것 은 e (a - > b), e (b - > c) = > e (a - > c) 즉 전달 관계 가 존재 하 는 것 이다. 이렇게 하면 관 계 를 전달 할 수 있다.물론 벨 맨 을 통 해 접근 성 있 는 전달 이 가능 하 다.하지만 실현 효율 이 낮은 것 은 분명 하 다.그래서 우 리 는 그림 을 많은 강 한 연결 분량 으로 줄 이 고 강 한 연결 분량 간 의 관 계 를 통 해 그 중의 모든 점 간 의 관 계 를 대표 할 수 있다. 그러면 귀 찮 게 변 의 관 계 를 전달 하지 않 고 모든 점 의 정 보 를 자신의 축소 점 에 맡 길 수 있다.S1 - > S2, 즉 S1 의 모든 점 에서 S2 까지 변 이 존재 하고 S2 - > S1 은 변 이 없다 (그렇지 않 으 면 S1, S2 는 하나의 강 한 연결 에 속한다). 분명히 S1 의 모든 점 은 sink 의 조건 에 부합 되 지 않 는 다.이 문 제 는 출도 가 없 는 강 한 연결 분량 의 모든 점 을 구하 기 위해 크기 에 따라 출력 하면 된다.
이 문 제 는 정말 줄 이지 않 고 P 배열 로 모든 점 이 처 한 강 한 연결 분량 의 레이 블 을 저장 하 는 것 이 관건 이다.각 점 의 각 변 의 관 계 를 통 해 만약 에 이 점 이 아웃 사 이 드 가 있 고 아웃 사 이 드 는 이 강 한 연결 을 다른 강 한 연결 로 연결 시 키 는 것 이다. 그래 야 이 강 한 연결 이 출 도 되 고 이 강 한 연결 표 시 를 다시 옮 겨 다 니 며 해당 되 는 출 도 없 는 강 한 연결 중의 점 을 출력 하면 된다.

//#include<iostream>
#include<stdio.h>
#include<stack>
#define MAXN 5005
using namespace std;

struct Node
{
       int v;
       Node *next;
}Edge[MAXN*MAXN],*ptr[MAXN];

int V,E;
int DFN[MAXN],LOW[MAXN],SCC[MAXN],P[MAXN];
bool visited[MAXN],inS[MAXN];
int SCCNum;
stack<int>myStack;
int min( int a,int b ){ return a<b?a:b; }

void addEdge( int u,int v,int num )
{
     Node *p=&Edge[num];
     p->v=v;
     p->next=ptr[u];
     ptr[u]=p;
}

int cnt;
void Tarjan(int pre)
{
     LOW[pre]=DFN[pre]=++cnt;
     Node *p=ptr[pre];
     myStack.push(pre);
     visited[pre]=true;
     inS[pre]=true;
     int u=pre;
     
     while( p )
     {
            if( !visited[p->v] )
            {
                Tarjan(p->v);
                LOW[u]=min( LOW[u],LOW[p->v] );
            }
            else if( inS[p->v] )
                 LOW[u]=min( LOW[u],DFN[p->v] );
            p=p->next;
     }
     if( DFN[u]==LOW[u] )
     {
         int v;
         SCCNum++;
         do {
             v=myStack.top();
             myStack.pop();
			 inS[v]=false;
             SCC[SCCNum]++;
             P[v]=SCCNum;           
         }while( u!=v );
     }
}
bool FINISH;
bool DFS( int pre )
{
     visited[pre]=true;
     int sum=0,i;
     for( i=1;i<=SCCNum;i++ )
          sum+=visited[i];
     if( sum==SCCNum )
         return FINISH=true;
     Node *p=ptr[pre];
     while( p )
     {
            if( !visited[p->v] )
                DFS(p->v);
            if( FINISH )
                return true;
            p=p->next;
     }
     return false;
}

int main()
{
    while( scanf( "%d",&V )!=EOF )
    {
           if( !V )
               break ;
           scanf( "%d",&E );
           int i,j;
           int u,v;
           for( i=0;i<=V;i++ )
                ptr[i]=NULL;
           cnt=0;SCCNum=0;FINISH=false;
           while( !myStack.empty() ) myStack.pop();
           
           for( i=1;i<=E;i++ )
           {
                scanf( "%d %d",&u,&v );
                addEdge( u,v,i );
           }
           
           memset( DFN,0,sizeof(DFN) );
           memset( LOW,0,sizeof(LOW) );
           memset( visited,0,sizeof(visited) );
           memset( inS,0,sizeof(inS) );
           
           for( i=1;i<=V;i++ )
                if( DFN[i]==0 ) 
					Tarjan(i);
                
           bool outD[MAXN];
           memset( outD,0,sizeof(outD) );
           for( int i=1;i<=V;i++ )
           {
                Node *p=ptr[i];
                while( p )
                {
                       if( P[i]!=P[p->v] )
                           outD[ P[i] ]=true;
                       p=p->next;
                }
           }
           for( i=1;i<=V;i++ )
           {
                if( outD[P[i]]==false )
                {
                    printf( "%d",i );break;
                }
           }
           for( i++;i<=V;i++ )
           {
                if( outD[P[i]]==false )
                printf( " %d",i );
           }
           printf( "
" );
    }
    return 0;
}