Cod sursa(job #1076341)

Utilizator calin13Calin Nicolau calin13 Data 10 ianuarie 2014 01:41:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#include <bitset>
#include <list>
#include <algorithm>
#include <string>
using namespace std;
#define INF 0xFFFFFFFF
unsigned int n, m , s, ans;
vector< list<unsigned int> > a(100005);
vector< unsigned int > d(100005);
bitset<100005> viz;
class cApp
{
public:
    cApp(const char *filename)
    {
        char inFile[30];
        strcpy(inFile, filename);
        strcat(inFile, ".in");
        char outFile[30];
        strcpy(outFile, filename);
        strcat(outFile, ".out");
        f.open(inFile, ios_base::in);
        g.open(outFile, ios_base::out);
    }
    ~cApp()
    {
        f.close();
        g.close();
    }
    void read()
    {
        f >> n >> m;
        unsigned int x, y;
        for (unsigned int i = 1; i <= m; ++i)
        {
            f >> x >> y;
            a[x].push_front(y);
            a[y].push_front(x);
        }
    }
    void write()
    {
        g << ans;
    }
    fstream f, g;
};

void dfs(unsigned int nod)
{
    if ( !viz[nod] )
    {
    viz[nod] = 1;
    for (list<unsigned int>::iterator it = a[nod].begin();
            it != a[nod].end(); ++it)
        dfs(*it);
    }
}
int main()
{
    cApp app("dfs");
    app.read();
    for (unsigned int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i), ++ans;
    app.write();
    return 0;
}