Pagini recente » Cod sursa (job #2502821) | Cod sursa (job #2163829) | Cod sursa (job #469893) | Cod sursa (job #2168024) | Cod sursa (job #875557)
Cod sursa(job #875557)
#include <stdio.h>
#include <string.h>
using namespace std;
struct nod{
int nr;
nod* next;
}*First[2][100005],*TList[100005];
int N,M,TMax;
int TF[100005],Time;
bool Exist[2][100005],T[100005];
void Insert(int x,int y){
if(First[0][x]==0){
First[0][x]=new nod;
First[0][x]->nr=y;
First[0][x]->next=0;
}
else{
nod *q=new nod;
q->nr=y;
q->next=First[0][x]->next;
First[0][x]->next=q;
}
if(First[1][y]==0){
First[1][y]=new nod;
First[1][y]->nr=x;
First[1][y]->next=0;
}
else{
nod *q=new nod;
q->nr=x;
q->next=First[1][y]->next;
First[1][y]->next=q;
}
}
void InsertIntoT(int x,int y){
if(TList[x]==0){
TList[x]=new nod;
TList[x]->nr=y;
TList[x]->next=0;
}
else{
nod *q=new nod;
q->nr=y;
q->next=TList[x]->next;
TList[x]->next=q;
}
}
void Read(){
freopen("ctc.in","r",stdin);
scanf("%d %d\n",&N,&M);
int i,x,y;
for(i=1;i<=M;i++){
scanf("%d %d\n",&x,&y);
Insert(x,y);
}
fclose(stdin);
}
void DF(int nr,int sw){
int nra;
Exist[sw][nr]=1;
if(sw==1){
if(Exist[0][nr]==1){
InsertIntoT(TMax,nr);
T[nr]=1;
}
}
nod *q=First[sw][nr];
while(q){
nra=q->nr;
if(T[nra]+Exist[sw][nra]==0)
DF(nra,sw);
q=q->next;
}
}
void Solve(){
int i,n=N;
for(i=1;i<=n;i++){
if(T[i]==0){
// memset(Exist[0],0,sizeof(Exist[0]));
// memset(Exist[1],0,sizeof(Exist[1]));
TMax++;
DF(i,0);
DF(i,1);
}
}
}
void Write(nod *p){
if(p){
printf("%d ",p->nr);
Write(p->next);
}
else
printf("\n");
}
void write(int t[]){
int i;
for(i=1;i<=N;i++)
printf("%d ",t[i]);
printf("\n");
}
int main()
{
Read();
Solve();
freopen("ctc.out","w",stdout);
printf("%d\n",TMax);
for(int i=1;i<=TMax;i++)
Write(TList[i]);
fclose(stdin);
return 0;
}