Pagini recente » Cod sursa (job #5463) | Cod sursa (job #767983) | Cod sursa (job #2100164) | Cod sursa (job #1816939) | Cod sursa (job #416226)
Cod sursa(job #416226)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define nmax 100010
int n, index, idx[nmax], low[nmax], cnt;
vector <int> g[nmax], ctc[nmax];
stack <int> s;
void tarjan(int nod)
{
int i;
idx[nod]=low[nod]=++index;
s.push(nod);
for (i=0; i<g[nod].size(); i++)
{
if (!idx[g[nod][i]]) tarjan(g[nod][i]);
if (idx[g[nod][i]]>=0)
low[nod]=min(low[nod], low[g[nod][i]]);
}
if (low[nod]==idx[nod])
{
cnt++;
do
{
i=s.top();
ctc[cnt].push_back(i);
idx[i]=-1;
s.pop();
}
while (i!=nod);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int m, i, j, x, y;
scanf("%d %d",&n,&m);
while (m--)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
}
for (i=1; i<=n; i++)
if (!idx[i]) tarjan(i);
printf("%d\n",cnt);
for (i=1; i<=cnt; i++)
{
for (j=0; j<ctc[i].size(); j++) printf("%d ",ctc[i][j]);
printf("\n");
}
}