Cod sursa(job #1267930)

Utilizator PhilipDumitruPhilip Dumitru PhilipDumitru Data 20 noiembrie 2014 14:55:35
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <list>
#include <stack>

using namespace std;

list <int> adiacList[100001];
char isVisited[100001];

int main()
{
    FILE * fin = fopen("dfs.in", "r");
    FILE * fout = fopen("dfs.out", "w");

    int m, n, i, j, x;
    fscanf(fin, "%d %d", &n, &m);
    while(m--)
    {
        fscanf(fin, "%d %d", &i, &j);
        adiacList[i].push_back(j);
        adiacList[j].push_back(i);
    }

    stack<int> st;
    list<int>::iterator it, it_end;
    for (x = 1, i = 0; x <= n; ++x)
    {
        if (!isVisited[x])
        {
            ++i;
            isVisited[x] = 1;
            st.push(x);
            while (!st.empty())
            {
                j = st.top();
                st.pop();
                for (it = adiacList[j].begin(), it_end = adiacList[j].end(); it != it_end; ++it)
                {
                    if (!isVisited[*it])
                    {
                        isVisited[*it] = i;
                        st.push(*it);
                    }
                }
            }
        }
    }
    fprintf(fout, "%d\n", i);

    fclose(fin);
    fclose(fout);
    return 0;
}