Cod sursa(job #1235210)

Utilizator afkidStancioiu Nicu Razvan afkid Data 28 septembrie 2014 23:26:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <vector>

using namespace std;
const char InFile[]="dfs.in";
const char OutFile[]="dfs.out";

class Graph
{
    int v;
    vector<int> *adj;
    int cnt;
    void DFSutil(int v,bool *visited);
public:
    Graph(int v);
    void addEdge(int v,int w);
    void DFS();
    int CNT();
};

Graph::Graph(int v)
{
    this->v=v;
    adj=new vector<int>[v];
    cnt=0;
}

void Graph::addEdge(int v,int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}

void Graph::DFSutil(int v,bool *visited)
{
    visited[v]=1;
    vector<int>::iterator it;
    for(it=adj[v].begin();it!=adj[v].end();++it)
        if(!visited[*it])
            DFSutil(*it,visited);
}
void Graph::DFS()
{
    bool visited[v];

    for(int i=1;i<v;++i)
        visited[i]=false;

    for(int i=1;i<v;++i)
        if(!visited[i])
        {
          ++cnt;
          DFSutil(i,visited);
        }
}

int Graph::CNT()
{
    return cnt;
}

int main()
{
    int a,b,n,m;
    freopen(InFile,"r",stdin);
    freopen(OutFile,"w",stdout);

    scanf("%d %d",&n,&m);
    Graph g(n+1);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&a,&b);
        g.addEdge(a,b);
    }
    g.DFS();
    printf("%d\n",g.CNT());
    return 0;
}