Pagini recente » Cod sursa (job #2069988) | Cod sursa (job #3002089) | Cod sursa (job #2206455) | Cod sursa (job #2698179) | Cod sursa (job #303177)
Cod sursa(job #303177)
#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;
}