Cod sursa(job #1338453)

Utilizator afkidStancioiu Nicu Razvan afkid Data 10 februarie 2015 02:15:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <vector>
#include <stack>
#define N 100010

using namespace std;

vector<int> arcs[N];
int visited[N];
int n,m;

int readInt()
{
    int n=0;
    char c = getchar();
    while(c<'0'|| c>'9') c=getchar();
    while(c>='0' && c<='9')
    {
        n=(n<<1)+(n<<3)+c-'0';
        c=getchar();
    }
    return n;
}

void ReadFile()
{
    freopen("dfs.in", "r", stdin);
    int a,b;
    n=readInt();
    m=readInt();
    for(int i=1;i<=m;++i)
    {
        a=readInt();
        b=readInt();
        arcs[a].push_back(b);
        arcs[b].push_back(a);
    }
    for(int i=1;i<=n;++i)
    {
        visited[i]=0;
    }
}

void Dfs(int nS)
{
    vector<int>::iterator it;
    stack<int> stk;
    stk.push(nS);
    visited[nS]=1;
    while(!stk.empty())
    {
        int p=stk.top();
        stk.pop();
        for(it=arcs[p].begin();it!=arcs[p].end();++it)
        {
            if(visited[*it]==0)
            {
                visited[*it]=1;
                stk.push(*it);
            }
        }
    }
}

void Solve()
{
    freopen("dfs.out", "w", stdout);
    int res=0;
    for(int i=1;i<=n;++i)
    {
        if(visited[i]==0)
        {
            Dfs(i);
            res++;
        }
    }
    printf("%d\n",res);
}

int main()
{
    ReadFile();
    Solve();
    return 0;
}