Cod sursa(job #2101011)

Utilizator serjiuuAvacaritei Sergiu serjiuu Data 6 ianuarie 2018 18:14:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <list>
#include <bitset>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int nmax=100005;

int n, m, k;
list <int> g[nmax];
bitset <nmax> viz;

void read_data()
{
    int x, y, i;

    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}
inline void dfs(int node)
{
    viz[node]=true;
    list <int> :: iterator it;
    for(it=g[node].begin();it!=g[node].end();it++)
        if(!viz[*it])
            dfs(*it);
}
void solve()
{
    int i;
    for(i=1;i<=n;i++)
        if(!viz[i])
        {
            dfs(i);
            k++;
        }
    fout<<k;
}
int main()
{
    read_data();
    solve();
    return 0;
}