Pagini recente » Cod sursa (job #161322) | Cod sursa (job #976268) | Cod sursa (job #1111913) | Cod sursa (job #1735393) | Cod sursa (job #899108)
Cod sursa(job #899108)
#include <cstdio>
#include <vector>
#define nlength 100011
#define SIZE 10000001
using namespace std;
int n,m,t;
vector<int>mylist[nlength];
vector<int>revlist[nlength];
int rev_seen[nlength],f[nlength],ff[nlength];
int my_seen[nlength],leader;
int iii,show[SIZE];
void compute_new_nodes()
{
for(int i=1;i<=n;i++)
{
vector<int>::iterator it;
for(it=revlist[i].begin();it!=revlist[i].end();it++)
{
mylist[f[*it]].push_back(f[i]);
}
}
}
int dfs_loop_my(int k)
{
vector<int>::iterator it;
for(it=mylist[k].begin();it!=mylist[k].end();it++)
{
if(!my_seen[*it])
{
iii++;
show[iii]=*it;
my_seen[*it]=1;
dfs_loop_my(*it);
}
}
}
int dfs_loop_rev(int k) // compute finishing times
{
vector<int>::iterator it;
for(it=revlist[k].begin();it!=revlist[k].end();it++)
{
if(!rev_seen[*it])
{
rev_seen[*it]=1;
dfs_loop_rev(*it);
}
}
t++;
f[k]=t;
ff[t]=k;
}
void read_data()
{
FILE *inFile;inFile=fopen("ctc.in","r");
fscanf(inFile,"%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
fscanf(inFile,"%d %d",&x,&y);
revlist[y].push_back(x); //graph G-reverse
}
fclose(inFile);
}
int main()
{
FILE *outFile;outFile=fopen("ctc.out","w");
read_data();
for(int i=n;i>=1;i--)
{
if(!rev_seen[i])
{
rev_seen[i]=1;
dfs_loop_rev(i);
}
}
compute_new_nodes();
int nr=0;
for(int i=n;i>=1;i--)
{
if(!my_seen[i])
{
nr++;
my_seen[i]=1;
show[++iii]=i;
dfs_loop_my(i);
show[++iii]=-1;
}
}
fprintf(outFile,"%d\n",nr);
iii=1;
for(int i=1;i<=nr;i++)
{
while(show[iii]!=-1)
{
fprintf(outFile,"%d ",ff[show[iii]]);
iii++;
}
iii++;
fprintf(outFile,"\n");
}
fclose(outFile);
return 0;
}