Pagini recente » Cod sursa (job #2291316) | Cod sursa (job #2546351) | Cod sursa (job #860360) | Cod sursa (job #982888) | Cod sursa (job #2465399)
#include <iostream>
#include <stack>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int MAXN = 1e5 + 5;
int viz[MAXN],nivel[MAXN],idk,iss[MAXN],n,L[MAXN],m,nrc;
vector < int > G[MAXN];
stack < int > s;
vector< int > ctc[MAXN];
void tarjan(int x) {
iss[x] = true;
viz[x] = true;
s.push(x);
nivel[x] = L[x] =++idk;
for ( auto y : G[x]) {
if ( !viz[y]) {
tarjan(y);
L[x] = min(L[y],L[x]);
}
else
if ( iss[y] )
L[x] = min(nivel[y],L[x]);
}
if (nivel[x] == L[x]) {
++nrc;
while ( !s.empty()) {
ctc[nrc].push_back(s.top());
iss[s.top()] = false;
int y = s.top();
s.pop();
if ( y == x)
break;
}
}
}
int main() {
fin >> n >> m;
for ( int x,y; m > 0; --m) {
fin >> x >> y;
G[x].push_back(y);
}
for ( int i = 1; i <= n; ++i)
if ( !viz[i])
tarjan(i);
fout << nrc << "\n";
for ( int i = 1; i <= nrc; ++i,fout << "\n")
for ( auto y : ctc[i])
fout << y << " " ;
}