Pagini recente » Cod sursa (job #1093852) | Monitorul de evaluare | Cod sursa (job #3214664) | Cod sursa (job #1696144) | Cod sursa (job #2708093)
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax = 100000;
vector <int> g[nmax+1];
int l[nmax+1], ll[nmax+1];
stack <int> s;
bitset<nmax+1> ins;
vector < vector <int> > sol;
void dfs( int x ) {
for ( int i = 0; i < int(g[x].size()); ++ i ) {
int xn = g[x][i];
if ( l[xn] == 0 ) {
l[xn] = l[x]+1;
ll[xn] = l[x]+1;
s.push(xn);
ins[xn] = 1;
dfs(xn);
if ( ll[xn] < ll[x] ) {
ll[x] = ll[xn];
}
} else if ( ins[xn] == 1 ) {
if ( ll[xn] < ll[x] ) {
ll[x] = ll[xn];
}
}
}
if ( ll[x] == l[x] ) {
int nsol = sol.size()+1;
sol.resize(nsol);
sol[nsol-1].resize(0);
while ( ins[x] == 1 ) {
int aux = s.top();
ins[aux] = 0;
s.pop();
sol[nsol-1].push_back(aux);
}
}
}
int main( ) {
int n, m;
fin >> n >> m;
for ( int i = 1; i <= m; ++ i ) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
}
for ( int i = 1; i <= n; ++ i ) {
if ( l[i] == 0 ) {
l[i] = 1;
ll[i] = 1;
s.push(i);
ins[i] = 1;
dfs(i);
}
}
fout << sol.size() << "\n";
for ( int i = 0; i < int(sol.size()); ++ i ) {
for ( int j = 0; j < int(sol[i].size()); ++j ) {
fout << sol[i][j] << " ";
}
fout << "\n";
}
return 0;
}