Cod sursa(job #2458476)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 20 septembrie 2019 18:26:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector <int> G[100001];
bool sel[100001];
int n,m,x,i,o,p,nr;
void df(int t)
{
    int i=0;
    sel[t]=true;
    for (i=0;i<G[t].size();++i)
        if (!sel[G[t][i]])
        df(G[t][i]);
}
bool cmp(int X,int Y)
{
    return X<Y;
}
int main()
{
    in>>n>>m;
    for (i=1;i<=m;++i)
    {
        in>>o>>p;
        G[o].push_back(p);
        G[p].push_back(o);

    }
    for(i=1; i<=n; i++)   sort(G[i].begin(),G[i].end());

    for (i=1;i<=n;++i)
    {
        if (sel[i]==0) {nr++; df(i); }
    }
    out<<nr;
    return 0;
}