Cod sursa(job #986558)

Utilizator rogoz.bogdanRogoz Bogdan rogoz.bogdan Data 19 august 2013 02:18:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
using namespace std;

#define nmax 100001

fstream fin("dfs.in", ios::in);
fstream fout("dfs.out", ios::out);

vector <int> A[nmax];

int dist[nmax];
bool viz[nmax];

int s[nmax],k;
int ras;

int N,M;

void DFS()
{
    int x,z;
    while(k>0)
    {
        x=s[k];
        if(A[x].size() > 0)
        {
            z=A[x].size();
            if(viz[A[x][z-1]] == 0)
            {
                viz[A[x][z-1]] = 1;
                s[++k]=A[x][z-1];
                dist[s[k]] = dist[x] + 1;

            }
            A[x].pop_back();
        }
        else k--;
    }
}

int main()
{
    int x,y,i;
    fin>>N>>M;
/*    k=1;
    s[k]=1;
    viz[1]=1;*/

    for(i=1; i<=M; i++)
    {
        fin>>x>>y;
        A[x].push_back(y);
        A[y].push_back(x);
    }

//    DFS();

    for(i=1; i<=N; i++)
    {
        if(viz[i]==0)
        {
            k=1;
            s[1]=i;
            viz[i]=1;
            DFS();
        }
    }

    for(i=1; i<=N; i++)
    {
        if(dist[i]==0) ras++;
//        fout<<dist[i]<<' ';
    }

    fout<<ras;

    fin.close(); fout.close();
    return 0;
}