Cod sursa(job #2263421)

Utilizator vladsirbu23Vlad Sirbu vladsirbu23 Data 18 octombrie 2018 17:48:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N,M,poz[100010],viz[100010],nr;
vector < vector< int> > v;
vector <int> a;
void dfs(int nod)
{
    int i;
    viz[nod]=1;
    for(i=0;i<v[poz[nod]].size();i++)
    {
        if(viz[v[poz[nod]][i]]==0)
        {
            dfs(v[poz[nod]][i]);
        }
    }
}
int main()
{
    int x,y,k,i;
    v.push_back(a);
    k=0;
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        if(poz[x]==0)
        {
            k++;
            v.push_back(a);
            poz[x]=k;
        }
        v[poz[x]].push_back(y);
        if(poz[y]==0)
        {
            k++;
            v.push_back(a);
            poz[y]=k;
        }
        v[poz[y]].push_back(x);
    }
    for(i=1;i<=N;i++)
    {
        if(viz[i]==0)
        {dfs(i);nr++;}
    }
    fout<<nr;
}