Pagini recente » Cod sursa (job #2538855) | Cod sursa (job #1369679) | Cod sursa (job #1674173) | Cod sursa (job #1847518) | Cod sursa (job #1219865)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define dim 100005
bool in_stack[dim];
stack <int> S;
vector <int> v[dim];
vector < vector <int> > SCC;
int lowlink[dim],idx[dim];
int curIdx = 0;
inline int min(int a,int b){
return (a>b?b:a);
}
void tarjan(int node){
lowlink[node] = idx[node] = ++curIdx;
S.push(node);
in_stack[node] = true;
for(int i = 0; i < v[node].size(); i++){
if(idx[v[node][i]] == 0){
tarjan(v[node][i]);
lowlink[node] = min(lowlink[v[node][i]],lowlink[node]);
}
else if(in_stack[v[node][i]]){
lowlink[node] = min(lowlink[v[node][i]],lowlink[node]);
}
}
if(lowlink[node] == idx[node]){
int u;
vector<int> SCC_node;
do{
u = S.top();
S.pop();
in_stack[u] = false;
SCC_node.push_back(u);
} while(u != node);
SCC.push_back(SCC_node);
}
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n,m;
scanf("%d %d\n",&n,&m);
for(int i = 1; i <= m; i++){
int a,b;
scanf("%d %d\n",&a,&b);
v[a].push_back(b);
}
for(int i = 1; i <= n; i++){
if(idx[i] == 0)
tarjan(i);
}
printf("%d\n",SCC.size());
for(int i = 0; i < SCC.size(); i++){
for(int j = 0; j < SCC[i].size(); j++){
printf("%d ",SCC[i][j]);
}
printf("\n");
}
}