Luogu p2683 신기 ac 코드 + Tarjan 템 플 릿

제목 링크
Tarjan 알고리즘
이것 은 그림 속 의 강 한 연결 분량 을 구 하 는 알고리즘 이다.강 한 연결 분량 은 이 서브 맵 의 모든 노드 가 서로 도착 할 수 있다 는 것 을 말한다.물론 Tarjan 의 효율 은 매우 높 고 시간 복잡 도 는 O (n + m) 이다.
여기 서 우 리 는 두 개의 관건 적 인 배열 을 사용 해 야 한다. 하 나 는 dfn 이 고 두부 뇌 라 고 부 르 며 모든 노드 가 dfs 에서 몇 번 째 로 검색 되 었 는 지 기록 하 는 것 이다. 또 하 나 는 low 이 고 모든 노드 의 뿌리 를 대표 하 며 바로 그의 강 한 연결 분량 의 시작 점 이다.
한 점 도 찾 아 본 적 이 없 으 면 계속 아래로 검색 하고 자신 에 게 가 는 점 dfn 을 업데이트 합 니 다.한 점 이 두 번 째 로 찾 혔 을 때, 그것 이 이미 강력 한 연결 분량 에 있다 는 것 을 증명 하기 때문에, 당신 을 찾 은 사람 을 뿌리 로 인정 해 야 합 니 다. (low 업데이트)
dfs 가 한 번 씩 검색 되 지 않 았 을 때 이 점 으로 계속 검색 하 세 요.
구체 적 인 코드 는 다음 과 같다.

#include
using namespace std;
inline int read(){
	int s=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())s=(s<<3)+(s<<1)+(c^48);
	return s*f;
}
inline void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
//       
int dfn[10001],low[10001],n,m,ans=0;  //dfn:          （   ）
//low：            ，       ，      ，like              。      LOW［］  ，           ，               。 
int visit[10001],tot;  //visit:          。tot：           
vector<int>v[10001];//    
stack<int>s;//  
void tarjan(int x)  
{  
     dfn[x]=low[x]=++tot;  //        dfn low         。 
     s.push(x); //   
     visit[x]=1;//   
    for(int i=0;i<v[x].size();i++)  
     {  
         if(!dfn[v[x][i]]) { //         （     dfn         ） 
             tarjan(v[x][i]); //      
             low[x]=min(low[x],low[v[x][i]]);  //  low 
        }  
        else if(visit[v[x][i]]){   //         
             low[x]=min(low[x],dfn[v[x][i]]); //      dfn       low 
        }  
     }  
     if(low[x]==dfn[x])  //            
    {  
    	int t=0;
        while(s.top()!=x){
        	t++;
        	visit[s.top()]=0;s.pop();
        }//   
        s.pop();visit[x]=0;
        if(t)ans++;//          
     }  
     return;  
}  
int main()  
{  
     n=read();m=read(); 
     for(int i=1;i<=m;i++)  
     {  
        int x=read(),y=read();
        v[x].push_back(y);//     
     }  
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);//                   tarjan 
    printf("%d
",ans);
    return 0;  
}  

다음은 현학 적 인 TarjanAC 코드 입 니 다.

#include
#define ______________________________ int
#define _____________________________ 10001
using namespace std;
inline ______________________________ read(){
       ______________________________ ___=0,_=1;char _______________________=getchar();
       while(!isdigit(_______________________)){if(_______________________=='-')_=-1;_______________________=getchar();}
       while(isdigit(_______________________)){___=___*10+_______________________-'0';_______________________=getchar();}
       return ___*_;
}
inline void write(______________________________ __________________){
       if(__________________<0){putchar('-');__________________=-__________________;}
       if(__________________>9)write(__________________/10);
       putchar(__________________%10+'0');
}
______________________________ ____________[_____________________________],_____________[_____________________________],n,m,________________=0;  
______________________________ ______________[_____________________________],_________________________,________________________;  
vector<______________________________>_____[_____________________________];
stack<______________________________>___;
void _______________(______________________________ __________________)  
{  
     ____________[__________________]=_____________[__________________]=++________________________;  
     ___.push(__________________); 
     ______________[__________________]=1;
    for(______________________________ i=0;i<_____[__________________].size();i++)  
     {  
         if(!____________[_____[__________________][i]]) { 
             _______________(_____[__________________][i]); 
             _____________[__________________]=min(_____________[__________________],_____________[_____[__________________][i]]);  
        }  
        else if(______________[_____[__________________][i]]){   
             _____________[__________________]=min(_____________[__________________],____________[_____[__________________][i]]); 
        }  
     }  
     if(_____________[__________________]==____________[__________________])  
    {  
    	______________________________ t=0;
        while(___.top()!=__________________){
        	t++;
        	______________[___.top()]=0;___.pop();
        }
        ___.pop();______________[__________________]=0;
        if(t)________________++;
     }  
     return;  
}  
______________________________ main()  
{  
     n=read();m=read(); 
     for(______________________________ i=1;i<=m;i++)  
     {  
        ______________________________ __________________=read(),y=read();
        _____[__________________].push_back(y); 
     }  
    for(______________________________ i=1;i<=n;i++)if(!____________[i])_______________(i);
    printf("%d
",________________);
    return 0;  
}