Pagini recente » Cod sursa (job #761714) | Cod sursa (job #1728331) | Profil NarTooN | Cod sursa (job #1311345) | Cod sursa (job #1900791)
#include <bits/stdc++.h>
#define maxN 100005
using namespace std;
vector<int> v[maxN];
bool seen[maxN];
int stk[maxN],top;
int idx[maxN],low[maxN]; /* tarjan's algorithm */
int n,m,i,j,x,y,level;
vector<vector<int> >ctc;
vector<int> aux;
void tarjan(int nod) /* dfs */
{
idx[nod]=low[nod]=++level;
low[nod]=level; /* smallest reachable idx */
stk[++top]=nod;
seen[nod]=true;
for(auto it:v[nod])
if(!idx[it]){
tarjan(it);
low[nod]=min(low[nod],low[it]);
}
else if(seen[it])
low[nod]=min(low[nod],idx[it]);
if(idx[nod]==low[nod])
{
int newn;
aux.clear();
do /* popping nodes in scc */
{
newn=stk[top--];
seen[newn]=false;
aux.push_back(newn);
}while(newn!=nod);
ctc.push_back(aux);
}
}
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",&x,&y),
v[x].push_back(y);
for(i=1;i<=n;i++)
if(!idx[i])
tarjan(i);
printf("%d\n",ctc.size()); /* printing components */
for(auto it:ctc)
{
for(auto nod:it)
printf("%d ",nod);
printf("\n");
}
return 0;
}