Cod sursa(job #1503532)

Utilizator Y0da1NUME JMECHER Y0da1 Data 16 octombrie 2015 13:58:58
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
//#include <iostream>
using namespace std;
/*int v[1001][1001], vf, nr=0, n;
void df(int k)
{
    //cout<<"Defeu!\n";
    int i=1;
    viz[k]=1;
    for(i=1;i<=n;i++)
    {
        if(!viz[i] && v[k][i] )
            df(i);
    }

}
int main()
{
    ifstream g ("dfs.in");
    ofstream h ("dfs.out");
    int m, x, y, i;
    g>>n>>m;
    for(i=0;i<m;i++)
    {
        //cout<<"Citire OK!\n";
        g>>x>>y;
        v[x][y]=1;
        v[y][x]=1;
    }
    //df-probabil recursiv
    for(i=1;i<=n;i++)
    {
        //cout<<"For OK!\n";
        if(!viz[i])
        {
            nr++;
            df(i);
        }
    }
    h<<nr;
}*/
int viz[100001];
class nod
{
public:
    int nr=0;
    int v[1000];

} a[100001];
void df(int k)
{
    int i=1;
    viz[k]=1;
    for(i=0;i<a[k].nr;i++)
    {
        if(!viz[a[k].v[i]] )
            df(a[k].v[i]);
    }
}
int main ()
{
    ifstream g ("dfs.in");
    ofstream h ("dfs.out");
    int m, n, x, y, i, j=0;
    g>>n>>m;
    for(i=0;i<m;i++)
    {
        //cout<<"Citire OK!\n";
        g>>x>>y;
        a[x].v[a[x].nr]=y;
            a[x].nr++;
        a[y].v[a[y].nr]=x;
            a[y].nr++;
    }
    for(i=1;i<=n;i++)
    {
        //cout<<"For OK!\n";
        if(!viz[i])
        {
            j++;
            df(i);
        }
    }
    //for(i=1;i<=n;i++)
       // cout<<viz[i]<<" ";
    h<<j;
    g.close();
    h.close();
    return 0;
}