Pagini recente » Cod sursa (job #2344659) | Cod sursa (job #39789) | Cod sursa (job #2399352) | Cod sursa (job #1079683) | Cod sursa (job #929477)
Cod sursa(job #929477)
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
#define max 100005
int n,m,nrc;
struct node
{
int index,lowlink,vis;
}nodes[max];
vector<int> roads[max],componente[max];
stack<int> S;
int ind;
void strongconnect(int v)
{
nodes[v].index=ind;
nodes[v].lowlink=ind;
nodes[v].vis=1;
ind+=1;
S.push(v);
for(vector<int>::iterator it=roads[v].begin();it!=roads[v].end();it++)
if(nodes[*it].vis==0)
{
strongconnect( *it );
nodes[v].lowlink= min(nodes[v].lowlink,nodes[*it].lowlink);
}
else
nodes[v].lowlink=min(nodes[v].lowlink,nodes[*it].lowlink);
if(nodes[v].lowlink==nodes[v].index)
{
int qw;
nrc++;
do
{
qw=S.top();
componente[nrc].push_back(qw);
S.pop();
} while( qw!=v );
}
}
void trajan()
{
ind=0;
for( int i=1;i<=n;i++)
if( nodes[i].index == 0 )
strongconnect( i );
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
roads[a].push_back(b);
}
trajan();
printf("%d\n",nrc);
for(int i=1;i<=nrc;i++)
{
for(vector<int>::iterator it=componente[i].begin(); it!=componente[i].end();it++)
printf("%d ",*it);
printf("\n");
}
return 0;
}