Cod sursa(job #303177)

Utilizator IeewIordache Bogdan Ieew Data 9 aprilie 2009 17:00:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
using namespace std;
#include <stdlib.h>
#define NMAX 100001
int *v[NMAX],*vt[NMAX],n,m,viz[NMAX],r[NMAX],q=0,nrcmp=0;
struct str
{int x,cmp;}w[NMAX];

void rec(int x)
{int i;
viz[x]=1;
for(i=1;i<=v[x][0];i++)
	if(!viz[v[x][i]])rec(v[x][i]);
r[n-q++]=x;
}

void rect(int x,int cmp)
{int i;
viz[x]=0;
w[x].x=x;w[x].cmp=cmp;

for(i=1;i<=vt[x][0];i++)
	if(viz[vt[x][i]])rect(vt[x][i],cmp);
}

int sortf(const void*a, const void*b)
{
  return ((str*)a)->cmp-((str*)b)->cmp;
}

int main()
{int i,a,b,c,j;
ifstream in("ctc.in");
in>>n>>m;
for(i=1;i<=m;i++)
{
 in>>a>>b;
 viz[a]++;
 r[b]++;
}
in.close();
for(i=1;i<=n;i++)
	{
	 v[i]=(int*)malloc((viz[i]+1)*sizeof(int));
	 vt[i]=(int*)malloc((r[i]+1)*sizeof(int));
	 v[i][0]=0;
	 vt[i][0]=0;
	 viz[i]=0;
	 r[i]=0;
	}
ifstream in2("ctc.in");
in2>>n>>m;
for(i=1;i<=m;i++)
	{
	 in2>>a>>b;
	 v[a][++v[a][0]]=b;
	 vt[b][++vt[b][0]]=a;
	}
in2.close();
//for(i=1;i<=n;i++){cout<<i<<"       ";
//for(j=1;j<=v[i][0];j++)cout<<v[i][j]<<' ';cout<<'\n';}

for(i=1;i<=n;i++)
	if(!viz[i])rec(i);
for(i=1;i<=n;i++)
	if(viz[r[i]])rect(r[i],++nrcmp);
qsort(w+1,n,sizeof(w[0]),sortf);
ofstream out("ctc.out");
out<<nrcmp;
for(i=1;i<=n;i++)
    {
        if(w[i].cmp!=w[i-1].cmp)out<<'\n';
        out<<w[i].x<<' ';
    }
    
out.close();
return 0;
}