Cod sursa(job #3252603)

Utilizator proflaurianPanaete Adrian proflaurian Data 30 octombrie 2024 10:57:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;
const int N = 100001;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,componente;
vector<int> v[N];
bitset<N> viz;
void BFS(int nod)
{
    queue<int> q;
    viz[nod]=1;
    q.push(nod);
    while(q.size())
    {
        nod=q.front();
        q.pop();
        for(auto vec:v[nod])
            if(!viz[vec])
        {
            viz[vec]=1;
            q.push(vec);
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    /// TOTUSI VOI FOLOSI BFS
    for(int i=1;i<=n;i++)
        if(!viz[i])
        {
            componente++;
            BFS(i);
        }
    g<<componente;
    return 0;
}