Pagini recente » Cod sursa (job #216729) | Cod sursa (job #655610) | Cod sursa (job #2908875) | Cod sursa (job #3233326) | Cod sursa (job #2381913)
#include <bits/stdc++.h>
#define NMAX 100010
//Algoritmul lui Tarjan pentru determinarea componentelor tare conexe
using namespace std;
vector <int> A[NMAX],CTC[NMAX],S;
int n,m,noc=0,idc=1,id[NMAX],low[NMAX];
bool in_stack[NMAX];
void Tarjan(int u){
S.push_back(u);
in_stack[u]=1;
id[u]=low[u]=idc++;
for(int i=0;i<A[u].size();i++){
int v=A[u][i];
if(!id[v]){
Tarjan(v);
}
if(in_stack[v])low[u]=min(low[u],low[v]);
}
if(id[u]==low[u]){
int c=S.back();
while(c!=u){
S.pop_back();
CTC[noc].push_back(c);
in_stack[c]=0;
c=S.back();
}
CTC[noc++].push_back(u);
S.pop_back();
}
}
int main(){
ifstream cin("ctc.in");
ofstream cout("ctc.out");
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
A[a].push_back(b);
}
for(int i=1;i<=n;i++){
if(!id[i])Tarjan(i);
}
cout<<noc<<'\n';
for(int i=0;i<noc;i++){
for(int j=0;j<CTC[i].size();j++){
cout<<CTC[i][j]<<' ';
}
cout<<'\n';
}
return 0;
}