Pagini recente » Cod sursa (job #10820) | Cod sursa (job #942373) | Cod sursa (job #2717377) | Cod sursa (job #502180) | Cod sursa (job #929511)
Cod sursa(job #929511)
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
#define mi(a,b) ((a)<(b) ? (a) : (b))
#define max 100005
int n,m,nrc;
struct node
{
int index,lowlink,vis;
node()
{
index=-1;
lowlink=0;
vis=0;
}
}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==-1)
{
strongconnect( *it );
nodes[v].lowlink= mi(nodes[v].lowlink,nodes[*it].lowlink);
}
else if( nodes[*it].vis==1 )
nodes[v].lowlink=mi(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=0;i<n;i++)
if( nodes[i].index == -1 )
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=0;i<m;i++)
{
scanf("%d%d",&a,&b);
roads[a-1].push_back(b-1);
}
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]+1);
printf("\n");
}
return 0;
}