Pagini recente » Cod sursa (job #764265) | Cod sursa (job #1740967) | Cod sursa (job #305664) | Cod sursa (job #8643) | Cod sursa (job #1503629)
#include <stdio.h>
#include <stack>
#include <vector>
#define MAX 100005
#define min(a, b) (((a) < (b)) ? (a) : (b))
using namespace std;
int n, m, i, j, x, y, index[MAX], lowlink[MAX], ind;
bool onStack[MAX];
stack<int> s;
vector<int> l[MAX], c;
vector< vector<int> > conex;
void tarjan(int x);
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
for(i = 0; i < m; i++){
scanf("%d%d", &x, &y);
l[x].push_back(y);
}
for(i = 1; i <= n; i++)
if(!index[i])
tarjan(i);
printf("%d\n", conex.size());
for(i = 0; i < conex.size(); i++){
for(j = 0; j < conex[i].size(); j++)
printf("%d ", conex[i][j]);
printf("\n");
}
return 0;
}
void tarjan(int x){
s.push(x);
lowlink[x] = index[x] = ind++;
onStack[x] = 1;
for(int i = 0; i < l[x].size(); i++)
if(!index[l[x][i]]){
tarjan(l[x][i]);
lowlink[x] = min(lowlink[x], lowlink[l[x][i]]);
}
else
lowlink[x] = min(lowlink[x], index[l[x][i]]);
if(lowlink[x] == index[x]){
int w;
c.clear();
do{
w = s.top(), s.pop();
c.push_back(w);
}while(w != x);
conex.push_back(c);
}
}