Pagini recente » Cod sursa (job #950087) | Cod sursa (job #1431197) | Cod sursa (job #1808090) | Cod sursa (job #2844253) | Cod sursa (job #2176370)
#include<cstdio>
#include<vector>
using namespace std;
int n,m;
int vec[100010],pos_in_vec[100010],pos;
int index[100010],lowlink[100010],max_index;
vector<int> adj[100010];
vector<int> ctc[100010];
int ctc_count;
int tarjan(int nod)
{
//printf("^ %d\n",nod);
max_index++;
index[nod]=max_index;
lowlink[nod]=max_index;
pos++;
pos_in_vec[nod]=pos;
vec[pos]=nod;
for(vector<int>::iterator it=adj[nod].begin();it!=adj[nod].end();it++)
{
if(index[*it]==0)
{
tarjan(*it);
lowlink[nod]=min(lowlink[nod],lowlink[*it]);
}
else if(pos_in_vec[*it]!=0)
{
lowlink[nod]=min(lowlink[nod],index[*it]);
}
}
//printf("*** %d %d %d\n",nod,lowlink[nod],index[nod]);
if(lowlink[nod]==index[nod])
{
int temp=pos;
pos=pos_in_vec[nod]-1;
ctc_count++;
for(int i=pos+1;i<=temp;i++)
{
ctc[ctc_count].push_back(vec[i]);
pos_in_vec[vec[i]]=0;
//printf(" $ %d %d\n",vec[i],i);
}
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
adj[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
if(index[i]==0)
{
tarjan(i);
}
}
printf("%d\n",ctc_count);
for(int i=1;i<=ctc_count;i++)
{
for(vector<int>::iterator it=ctc[i].begin();it!=ctc[i].end();it++)
{
printf("%d ",*it);
}
printf("\n");
}
}