Pagini recente » Cod sursa (job #1920994) | Cod sursa (job #132437) | Cod sursa (job #1675048) | Cod sursa (job #1986219) | Cod sursa (job #2428462)
#include<fstream>
using namespace std;
int a[101][101],n,m,i,j,x,y,s[100],p[101],ctc[101],nrc;
ifstream f("ctc.in");
ofstream g("ctc.out");
void df1(int nod)
{
int j;
s[nod]=1;
for(j=1;j<=n;j++)
if(a[nod][j]==1&&s[j]==0)
df1(j);
}
void df2(int nod)
{
int j;
p[nod]=1;
for(j=1;j<=n;j++)
if(a[j][nod]==1&&p[j]==0)
df2(j);
}
int main()
{
int i,j;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x;
f>>y;
a[x][y]=1;
}
nrc=0;
for(i=1;i<=n;i++)
if(ctc[i]==0) //DACA NODUL I NU APARTINE NICIUNEI COMPONENTE CONEXE
{
for(j=1;j<=n;j++)
s[j]=p[j]=0;//resetez aparitiile
df1(i);df2(i);
nrc++;//daca componenta i nu aprtine nicunei componente conexe inseamna ca chiar ea poate sa fie una si verific asta in cele ce urmeaza
for(j=1;j<=n;j++)
if(s[j]==1&&p[j]==1)
ctc[j]=nrc;//nodul j apartine componentei conexe cu nr de ordine nrc
}
g<<nrc<<endl;
int pivot=1;
while(pivot<=nrc)
{for(i=1;i<=n;i++)
if(ctc[i]==pivot)
g<<i<<" ";
g<<endl;
pivot++;
}
f.close();
g.close();
return 0;
}