Pagini recente » Cod sursa (job #2565627) | Cod sursa (job #3254140) | Cod sursa (job #1424821) | Cod sursa (job #527623) | Cod sursa (job #1550394)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <deque>
#define NN 100001
//#define x first
//#define y second
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int lowidx[NN],in_stack[NN],idx[NN],indexx,n,m,i,j;
vector < int > v[NN],curent;
vector < vector <int> > solutii;
stack <int> S;
void tarjan(int nod)
{
int i;
indexx ++;
lowidx[nod] = idx[nod] = indexx;
S.push(nod);
in_stack[nod] = 1;
for(i = 0; i < v[nod].size(); i ++)
{
int nxt = v[nod][i];
if(!idx[nxt])
{
tarjan(nxt);
lowidx[nod] = min(lowidx[nod], lowidx[nxt]);
}
else if(in_stack[nxt])
{
lowidx[nod] = min(lowidx[nod], lowidx[nxt]);
}
}
if(lowidx[nod] == idx[nod])
{
int now;
do
{
now=S.top();
curent.push_back(now);
in_stack[now]=0;
S.pop();
}while(now != nod);
solutii.push_back(curent);
curent.clear();
}
}
int main()
{
fin >> n >> m;
for(i = 1; i <= m; i ++)
{
int a,b;
fin >> a >> b;
v[a].push_back(b);
}
for(i = 1; i <= n; i ++)
{
if(!idx[i])
tarjan(i);
}
fout << solutii.size() << '\n';
for(i = 0; i < solutii.size(); i ++, fout << '\n')
for(j = 0; j < solutii[i].size(); j ++)
fout << solutii[i][j] << ' ';
return 0;
}