Pagini recente » Cod sursa (job #161684) | Cod sursa (job #2012758) | Cod sursa (job #166653) | Cod sursa (job #1571889) | Cod sursa (job #1610049)
#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int low[100010], niv[100010], N, M, x, y, a, nr;
vector<int>L[100010], SOL[100010];
bitset<100010>v, X;
deque<int>Q;
void dfs(int nod)
{
v[nod] = 1;
X[nod] = 1;
Q.push_back(nod);
low[nod] = niv[nod] = ++a;
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] ]);
}
else
{
if(X[ L[nod][i] ] == 1)
{
low[nod] = min(low[nod], low[ L[nod][i] ]);
}
}
}
if(low[nod] == niv[nod])
{
nr ++;
while(Q.back() != nod)
{
int b = Q.back();
Q.pop_back();
SOL[nr].push_back(b);
X[b] = 0;
}
Q.pop_back();
SOL[nr].push_back(nod);
X[nod] = 0;
}
}
int main()
{
fin >> N >> M;
for(int i = 1; i <= M; i ++)
{
fin >> x >> y;
L[x].push_back(y);
}
for(int i = 1; i <= N; i ++)
{
if(v[i] == 0)
{
dfs(i);
}
}
fout << nr << '\n';
for(int i = 1; i <= nr; i ++)
{
for(int j = 0; j < SOL[i].size(); j ++)
{
fout << SOL[i][j] << " ";
}
fout << '\n';
}
return 0;
}