Pagini recente » Cod sursa (job #1147982) | Cod sursa (job #1554630) | Cod sursa (job #1769631) | Cod sursa (job #2296764) | Cod sursa (job #301932)
Cod sursa(job #301932)
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define nm 100010
vector <int> v[nm], sol[nm];
stack <int> q;
vector <int>::iterator j;
int n, m, i, nrctc, x, y;
int ind[nm], indx, ll[nm], inq[nm];
inline int mn(int a, int b) { return (a < b ? a : b); }
void tarjan(int p)
{
vector <int>::iterator it;
ind[p] = indx;
ll[p] = indx;
++indx;
q.push(p);
inq[p] = 1;
for(it=v[p].begin(); it!=v[p].end(); ++it)
{
if (ind[*it] == -1)
{
tarjan(*it);
ll[p] = mn(ll[p], ll[*it]);
}
else
if (inq[*it])
{
ll[p] = mn(ll[p], ll[*it]);
}
}
if (ll[p] == ind[p])
{
int tmp;
++nrctc;
do
{
tmp = q.top();
sol[nrctc].push_back(tmp);
q.pop();
inq[tmp] = 0;
}
while (tmp != p);
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d ", &n, &m);
for (i=1; i<=n; ++i)
{
ind[i] = -1;
}
indx = 0;
for (i=1; i<=m; ++i)
{
scanf("%d %d ", &x, &y);
v[x].push_back(y);
}
for (i=1; i<=n; ++i)
{
if (ind[i] == -1)
{
tarjan(i);
}
}
printf("%d\n", nrctc);
for (i=1; i<=nrctc; ++i)
{
for (j=sol[i].begin(); j!=sol[i].end(); ++j)
{
printf("%d ", *j);
}
printf("\n");
}
return 0;
}