Pagini recente » Cod sursa (job #235674) | Cod sursa (job #2822266) | Cod sursa (job #1264500) | Cod sursa (job #1379186) | Cod sursa (job #2450651)
#include<iostream>
#include<fstream>
using namespace std;
int a[101][101],n,m,i,j,x,y,s[100],p[101],ctc[101],nrc,sol[100][100];
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;
}
/* cout<<"Matricea de adiacenta e:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
cout<<endl<<endl;*/
nrc=0;
int k=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
sol[nrc][++k]=j;
}
k=0;
}
g<<nrc<<'\n';
for(i=1;i<=nrc;i++)
{
for(j=1;j<=n;j++)
if(sol[i][j]==0)
break;
else
g<<sol[i][j]<<" ";
g<<'\n';
}
return 0;
}