Pagini recente » Cod sursa (job #2453236) | Cod sursa (job #2268094) | Cod sursa (job #929504)
Cod sursa(job #929504)
#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;
stack<int> S;
vector<vector<int>> final;
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].index==0)
{
strongconnect( *it );
nodes[v].lowlink= min(nodes[v].lowlink,nodes[*it].lowlink);
}
else if( nodes[*it].vis==1 )
nodes[v].lowlink=min(nodes[v].lowlink,nodes[*it].lowlink);
if(nodes[v].lowlink==nodes[v].index)
{
int qw;
componente.clear();
do
{
qw=S.top();
componente.push_back(qw);
nodes[qw].vis=0;
S.pop();
} while( qw!=v );
final.push_back(componente);
}
}
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",final.size());
for(size_t i=0;i<final.size();i++)
{
for(size_t j=0;j<final[i].size();j++)
printf("%d ",final[i][j]);
printf("\n");
}
return 0;
}