Cod sursa(job #2500515)

Utilizator CatalinaPHOVornicu Catalina-Cristina CatalinaPHO Data 28 noiembrie 2019 09:36:22
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>

using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int a[101][101],n,m,viz[100001],i,x,y,nod,s=0,z,j,v[10001],nr;
void dfs(int nod)
{
    int i;
    viz[nod]=1;
    for(i=1;i<=n;i++)
        if(viz[i]==0&&a[nod][i]==1)
        dfs(i);
}
int main()
{
    cin>>n>>m;
    while(cin>>x>>y)
        a[x][y]=a[y][x]=1;
        while(i<=n)
            {
        for(z=1;z<n;z++)
        {
            for(j=z+1;j<=n;j++)
                if(a[i][j]==1&&a[i][z]==1)
                    a[z][j]=a[j][z]=1;
        }
        i++;
            }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            {
        dfs(i);
        nr++;
            }
            cout<<nr;
    return 0;
}