Pagini recente » Cod sursa (job #1710431) | Cod sursa (job #1938271) | Cod sursa (job #3213253) | Cod sursa (job #1812534) | Cod sursa (job #1958946)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> v[100003];
int disc[100003];
int low[100003];
int tim;
stack<int> S;
vector<int> s[100003];
bitset<100003> ins;
int C;
void dfs(int nod) {
disc[nod] = ++tim;
low[nod] = disc[nod];
S.push(nod);
ins[nod] = true;
for(int i = 0; i < v[nod].size(); i++) {
if(disc[v[nod][i]] == 0) {
dfs(v[nod][i]);
low[nod] = min(low[nod], low[v[nod][i]]);
} else if(ins[v[nod][i]])
low[nod] = min(low[nod], low[v[nod][i]]);
}
if(low[nod] == disc[nod]) {
C++;
int Q = S.top();
while(Q != nod) {
Q = S.top();
ins[Q] = false;
s[C].push_back(Q);
S.pop();
}
}
}
int main() {
int n,m;
in >> n >> m;
int x,y;
for(int i = 1; i <= m; i++) {
in >> x >> y;
v[x].push_back(y);
}
for(int i = 1; i <= n; i++)
if(disc[i] == 0)
dfs(i);
out << C << '\n';
for(int i = 1; i <= C; i++) {
for(int j = 0; j < s[i].size(); j++) {
out << s[i][j] << " ";
}
out << '\n';
}
return 0;
}