Pagini recente » Cod sursa (job #2530820) | Cod sursa (job #2632335) | Cod sursa (job #2495588) | Cod sursa (job #2222352) | Cod sursa (job #574126)
Cod sursa(job #574126)
#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 N, M, idx[NMAX], lowlink[NMAX], index;
stack <int> S;
bool in_stack[NMAX];
void tarjan(int nod){
index++;
idx[nod] = lowlink[nod] = index;
S.push(nod);
in_stack[nod] = true;
for (int i = 0; i < G[nod].size(); i++)
if(!idx[i]){
tarjan(i);
lowlink[nod] = min(lowlink[nod], lowlink[i]);
}
else{
if (in_stack[i])
lowlink[nod] = min(lowlink[nod], lowlink[i]);
}
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 << endl;
for (int i = 0; i < n; i++){
m = printer[i].size();
for (int j = 0; j < m; j++)
cout << printer[i][j]<< " ";
cout << endl;
}
return 0;
}