Pagini recente » Cod sursa (job #1166731) | Cod sursa (job #2849202) | Cod sursa (job #1472198) | Cod sursa (job #2525524) | Cod sursa (job #769947)
Cod sursa(job #769947)
#include<iostream>
#include<stdio.h>
#include<stack>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
#define max 100005
#define Min(a, b) ((a) < (b) ? (a) : (b))
vector <int> adj[max],con,id,lowlink,in_stack;
vector < vector<int> > G;
stack <int>S;
int index,n;
void citire();
void afisare();
void tarjan(int);
int main()
{
citire();
id.resize(n),lowlink.resize(n),in_stack.resize(n);
id.assign(n,-1),in_stack.assign(n,0);
for(int i=0;i<n;++i)
if(id[i] == -1)
tarjan(i);
afisare();
return 0;
}
void citire()
{
freopen("ctc.in","r",stdin);
int nr,x,y;
scanf("%d",&n);
for(scanf("%d",&nr);nr > 0; --nr)
scanf("%d%d",&x,&y),
adj[x-1].push_back(y-1);
}
void afisare()
{
freopen("ctc.out","w",stdout);
printf("%d\n",int(G.size()));
for(unsigned int i=0;i<G.size();++i){
for(unsigned int j=0;j<G[i].size();++j)
printf("%d ",int(G[i][j])+1);
printf("\n");
}
}
void tarjan(int i)
{
id[i]=lowlink[i]=index;
++index;
S.push(i),in_stack[i]=1;
vector <int>::const_iterator it;
for(it = adj[i].begin();it != adj[i].end(); ++it)
{
if(id[*it] == -1)
tarjan(*it),
lowlink[i]=Min(lowlink[i],lowlink[*it]);
else if(in_stack[*it])
lowlink[i]=Min(lowlink[i],lowlink[*it]);
}
if(id[i]==lowlink[i])
{
con.clear();
int nod;
do {
con.push_back(nod = S.top());
S.pop(),in_stack[nod]=0;
}while(nod!=i);
G.push_back(con);
}
}