Pagini recente » Cod sursa (job #1021276) | Sandbox (cutiuţa cu năsip) | Cod sursa (job #1723877) | Cod sursa (job #1129157) | Cod sursa (job #2450652)
#include<iostream>
#include<fstream>
using namespace std;
const int NLIM=10001;
int a[NLIM][NLIM],n,m,i,j,x,y,s[NLIM*NLIM],p[NLIM*NLIM],ctc[NLIM*NLIM],nrc,sol[NLIM][NLIM];
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;
}