Cod sursa(job #1108282)

Utilizator tac1234Tran Bach Nguyen tac1234 Data 15 februarie 2014 15:39:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <vector>
#include <cstdio>
using namespace std;
bool viz[100005]; /// vector de verificat daca e vizitat
vector <int> g[100001]; /// graful
void dfs(int n) /// functia dfs
{
    int l,i;
    l=g[n].size();
    for(i=0; i<l; ++i)
    {
        if (!viz[g[n][i]])
        {
            viz[g[n][i]]=true;
            dfs(g[n][i]);
        }
    }
}
int rez; /// rezultatul
int main ()
{
    ///freopen("dfs.in","r",stdin);
    ///freopen("dfs.out","w",stdout);
    int n,m,i,a,b;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; ++i)
    {
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
        /// face graful
    }
    for(i=1; i<=n; ++i)
    {
        if (!viz[i]) /// daca nu l-a vizitat inca
        {
            viz[i]=true; /// il pune ca la vizitat
            dfs(i); /// aplica functia dfs([int]);
            ++rez;
        }
    }
    printf("%d\n",rez);
    return 0;
}