Cod sursa(job #3126041)

Utilizator tudorbuhniaTudor Buhnia tudorbuhnia Data 5 mai 2023 12:55:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> v[100005];
bool vis[100005];
void edge(int a, int b)
{
    v[a].push_back(b);
    v[b].push_back(a);
}
void dfs(int n)
{
    stack<int> st;
    st.push(n);
    vis[n]=1;
    while(!st.empty())
    {
        int t=st.top();
        int ch=0;
        for(auto x : v[t])
        {
            if(vis[x]==0)
            {
                st.push(x);
                vis[x]=1;
                ch=1;
                break;
            }
        }
        if(ch==0)
            st.pop();
    }
}
int main()
{
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    int n, m, a, b, r=0;
    in >> n >> m;
    for(int i=0;i<m;i++)
    {
        in >> a >> b;
        edge(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            dfs(i);
            r++;
        }
    }
    out << r;
    return 0;
}