Cod sursa(job #1503635)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 16 octombrie 2015 17:44:20
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#include<stack>
#include<vector>
#define MAX 100005
#define pb push_back
#define k(a,b)(((a)<(b))?(a):(b))
using namespace std;int n,m,i,j,x,y,a[MAX],z[MAX],ind;bool o[MAX];stack<int>s;vector<int>l[MAX],c;vector<vector<int> >C;void t(int x);int main(){freopen("ctc.in","r",stdin);freopen("ctc.out","w",stdout);scanf("%d%d",&n,&m);for(i=0;i<m;i++){scanf("%d%d",&x,&y);l[x].pb(y);}for(i=1;i<=n;i++)if(!a[i])t(i);printf("%d\n",C.size());for(i=0;i<C.size();i++){for(j=0;j<C[i].size();j++)printf("%d ",C[i][j]);printf("\n");}return 0;}void t(int x){s.push(x);z[x]=a[x]=ind++;o[x]=1;for(int i=0;i<l[x].size();i++)if(!a[l[x][i]]){t(l[x][i]);z[x]=k(z[x],z[l[x][i]]);}else z[x]=k(z[x],a[l[x][i]]);if(z[x]==a[x]){int w;c.clear();do{w=s.top(),s.pop();o[w]=0;c.pb(w);}while(w!=x);C.pb(c);}}