Pagini recente » Cod sursa (job #2989000) | Cod sursa (job #2215435) | Cod sursa (job #2248398) | Cod sursa (job #2784483) | Cod sursa (job #1499520)
#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, ind = 1, index[MAX], lowlink[MAX];
bool onStack[MAX];
vector<int> l[MAX], c;
vector< vector<int> > conex;
stack<int> s;
void ctc(int v);
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])
ctc(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 ctc(int v){
int w;
index[v] = ind;
lowlink[v] = ind++;
s.push(v);
onStack[v] = 1;
for(int i = 0; i < l[v].size(); i++){
if(!index[l[v][i]]){
ctc(l[v][i]);
lowlink[v] = min(lowlink[v], lowlink[l[v][i]]);
}
else if(onStack[l[v][i]])
lowlink[v] = min(lowlink[v], index[l[v][i]]);
}
if(lowlink[v] == index[v]){
do{
w = s.top();
s.pop();
onStack[w] = 0;
c.push_back(w);
}while(v != w);
conex.push_back(c);
c.clear();
}
}