Cod sursa(job #2134396)

Utilizator rares_ciocieaRares Andrei Ciociea rares_ciociea Data 17 februarie 2018 21:53:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <vector>

using namespace std;
vector <int> g[100001];
bool ap[100001];
ifstream in("dfs.in");
ofstream out("dfs.out");
void dfs(int a)
{
    ap[a]=1;int i;
    for(i=0;i<g[a].size();i++)
    {
        if(ap[g[a][i]]==0)
        {
            dfs(g[a][i]);
        }
    }
}
int main()
{
    int n,m,i,nod1,nod2,cnt=0;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>nod1>>nod2;
        g[nod1].push_back(nod2);
        g[nod2].push_back(nod1);
    }
    for(i=1;i<=n;i++)
    {
        if(ap[i]==0)
        {
            dfs(i);
            cnt++;
        }
    }
    out<<cnt;
    return 0;
}