Pagini recente » Cod sursa (job #722596) | Cod sursa (job #2770906) | Cod sursa (job #1910717) | Cod sursa (job #1718450) | Cod sursa (job #1862248)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct Nod
{
int info;
Nod *next;
};
Nod *lista[100001],*listaT[100001];
int n, m, nrctc, pred[100001], succ[100001];
void citire()
{
f>>n>>m;
int i, x, y;
for (i = 1; i <= m; i++)
{
f>>x>>y;Nod *p=new Nod;p->next=lista[x];p->info=y;lista[x]=p;
p=new Nod;p->next=listaT[y];p->info=x;listaT[y]=p;
}
}
void df_succesor(int nod) //det multimea succesorilor lui nod
{
succ[nod] = nrctc;
for(Nod *p=lista[nod];p!=NULL;p=p->next)
if (succ[p->info]==0) df_succesor(p->info);
}
void df_pred(int nod) //det multimea predecesorilor lui nod
{
pred[nod] = nrctc;
for(Nod *p=listaT[nod];p!=NULL;p=p->next)
if (pred[p->info]==0) df_pred(p->info);
}
void intersectie()//pastreaza doar nodurile i care au pred[i]=succ[i]
{
for(int i=1;i<=n;i++)
if(pred[i]!=succ[i]) pred[i]=succ[i]=0;
}
int main()
{
citire();int i,j;
nrctc=1;
for(i=1;i<=n;i++)
if(succ[i]==0)
{
succ[i]=nrctc;
df_succesor(i);df_pred(i);
intersectie();
nrctc++;
}
g<<nrctc-1<<"\n";
for(i=1;i<nrctc;i++)
{
for(j=1;j<=n;j++)
if(succ[j]==i)g<<j<<' ';
g<<"\n";
}
f.close();g.close();return 0;
}