Pagini recente » Cod sursa (job #1771161) | Cod sursa (job #972562) | Cod sursa (job #978741) | Cod sursa (job #325129) | Cod sursa (job #2085020)
#include <bits/stdc++.h>
#define MN 100005
#define MM 200005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int N, M, ns, k, post[MN];
bitset <MN> viz;
typedef struct nod
{
int vf;
nod* next;
} *pnod;
pnod G[MN], Gt[MN], Sol[MN];
void add(pnod graf[], int a, int b)
{
pnod p = new nod;
p->vf = b;
p->next = graf[a];
graf[a] = p;
}
void add(pnod &graf, int x)
{
pnod p = new nod;
p->vf = x;
p->next = graf;
graf = p;
}
void dfs(int nod)
{
viz.set(nod);
for(pnod p = G[nod]; p; p = p->next)
if(!viz.test(p->vf))
dfs(p->vf);
post[++k] = nod;
}
void dfsT(int nod)
{
viz.set(nod, 0);
add(Sol[ns], nod);
for(pnod p = Gt[nod]; p; p = p->next)
if(viz.test(p->vf))
dfsT(p->vf);
}
int main()
{
in >> N >> M;
for(int a, b, i = 1; i <= M; ++i)
{
in >> a >> b;
add(G, a, b);
add(Gt, b, a);
}
for(int i = 1; i <= N; ++i)
if(!viz.test(i))
dfs(i);
for(int i = k; i; --i)
if(viz.test(post[i]))
{
ns++;
dfsT(post[i]);
}
out << ns << '\n';
for(int i = 1; i <= ns; ++i)
{
for(pnod p = Sol[i]; p; p = p->next)
out << p->vf << ' ';
out << '\n';
}
in.close(), out.close();
return 0;
}