Cod sursa(job #1504845)

Utilizator Y0da1NUME JMECHER Y0da1 Data 18 octombrie 2015 14:22:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <iostream>
#include <vector>
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;
    vector <int> v;

} 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.push_back(y);
            a[x].nr++;
        a[y].v.push_back(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]<<" ";
    //cout<<sizeof(a)<<" "<<sizeof(viz);
    h<<j;
    g.close();
    h.close();
    return 0;
}