Pagini recente » Cod sursa (job #3030378) | Cod sursa (job #1235708) | Cod sursa (job #2175436) | Cod sursa (job #83288) | Cod sursa (job #574139)
Cod sursa(job #574139)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100000
using namespace std;
vector <int> G[NMAX], ctc;
vector < vector <int> > printer;
int idx[NMAX], lowlink[NMAX], ind;
stack <int> S;
bool in_stack[NMAX];
void tarjan(int nod){
++ind;
idx[nod] = lowlink[nod] = ind;
S.push(nod);
in_stack[nod] = true;
vector <int>::const_iterator it;
for (it = G[nod].begin(); it != G[nod].end(); ++it)
if(!idx[*it]){
tarjan(*it);
lowlink[nod] = min(lowlink[nod], lowlink[*it]);
}
else{
if (in_stack[*it])
lowlink[nod] = min(lowlink[nod], lowlink[*it]);
}
if (idx[nod] == lowlink[nod]){
int aux;
ctc.clear();
do {
aux = S.top();
S.pop();
in_stack[aux] = false;
ctc.push_back(aux);
} while (aux != nod);
printer.push_back(ctc);
}
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
G[x].push_back(y);
}
for (int i = 0; i < n; i++)
if (!idx[i])
tarjan(i);
n = printer.size();
cout << n << "\n";
for (int i = 0; i < n; ++i){
m = printer[i].size();
for (int j = 0; j < m; ++j)
cout << printer[i][j]<< " ";
cout << "\n";
}
return 0;
}