Pagini recente » Cod sursa (job #2199541) | Autentificare | Cod sursa (job #1497107) | Cod sursa (job #532898) | Cod sursa (job #1346591)
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int nivel[100010], low[100010];
int i, j, niv, n, m, x, y, nr, w;
vector <int> L[100010], P[100010];
stack <int> S;
bitset <100010> v;
bitset <100010> X;
void dfs(int nod){
v[nod] = 1;
nivel[nod] = low[nod] = niv;
niv++;
S.push(nod);
X[nod] = 1;
for(int i = 0; i < L[nod].size(); i ++){
if(v[ L[nod][i] ] == 0){
dfs(L[nod][i]);
low[nod] = min(low[nod], low[ L[nod][i] ]);
}
if( X[ L[nod][i] ] )
low[nod] = min(low[nod], low[ L[nod][i] ]);
}
if(low[nod] == nivel[nod]){
nr++;
do{
X[ S.top() ] = 0;
w = S.top();
S.pop();
P[nr].push_back( w );
}while(w != nod);
}
}
int main()
{
fin >> n >> m;
for(i = 1; i <= m; i++)
{
fin >> x >> y;
L[x].push_back(y);
}
niv = 1;
for(i = 1; i <= n; i ++)
if(!v[i])
dfs(i);
fout << nr << '\n';
for(i = 1; i <= nr; i ++){
for(j = 0; j < P[i].size(); j ++)
fout << P[i][j] << " ";
fout << '\n';
}
return 0;
}