Pagini recente » Istoria paginii onis-2016/clasament/runda-2 | Cod sursa (job #1553816) | Cod sursa (job #1127430) | Cod sursa (job #1344353) | Cod sursa (job #383807)
Cod sursa(job #383807)
#include <stdio.h>
#include <vector>
#include <cstring>
using namespace std;
#define maxn 100100
#define pb push_back
long n, m, i, j, k, sol, a, b, f[maxn], st[maxn], st2[maxn], u[maxn];
vector<long> v[maxn], vi[maxn];
void df(long nod)
{
if(f[nod]) return;
long y;
f[nod]=1;
for(y=0; y<v[nod].size(); y++)
df(v[nod][y]);
st[++st[0]]=nod;
}
void df2(long nod, long who)
{
if(f[nod]) return;
long y=0;
f[nod]=1;
u[nod]=who;
for(y=0; y<vi[nod].size(); y++)
df2(vi[nod][y], who);
st2[++st2[0]]=nod;
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
for(i=1; i<=m; i++)
{
scanf("%d%d", &a, &b);
v[a].pb(b);
vi[b].pb(a);
}
for(i=1; i<=n; i++)
if(!f[i])
df(i);
memset(f, 0, sizeof(f));
for(i=n; i; --i)
if(!f[st[i]])
{
df2(st[i], st[i]);
sol++;
}
printf("%d\n", sol);
for(i=1; i<=n; i++)
{
printf("%d ", st2[i]);
if(u[st2[i]]!=u[st2[i+1]])
printf("\n");
}
return 0;
}