Cod sursa(job #2782404)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 12 octombrie 2021 12:56:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3 kb
#include<bits/stdc++.h>
using namespace std;

const int inf=(1e9);

const int dim=(1e5);

char buff[dim+5];

int pos=0;

void read(int &nr)
{
    int semn=1;
    nr=0;


    while(!isdigit(buff[pos]))
    {

        if(buff[pos]=='-') semn=-1;

        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }


    }


    while(isdigit(buff[pos]))
    {
        nr=nr*10+buff[pos]-'0';
        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }
    }

    nr*=semn;

}

class Graph
{

private:

    int m_nodes;

    vector< vector< pair<int,int> > > m_adjList;

    vector<pair<int, pair<int,int> > > m_edges;

    vector<bool> m_visited;

    bool m_areLabeled;

public:

    Graph(int nodes,bool areLabeled)
    {
        m_nodes=nodes;
        m_areLabeled=areLabeled;

        m_adjList.resize(nodes+5);

    }


    void addEdge(int from, int to, int cost)
    {
        m_adjList[from].push_back(make_pair(to,cost));
        m_edges.push_back(make_pair(from,make_pair(to,cost)));
    }

    void resetVisited()
    {
        m_visited.resize(m_nodes+5);

        for(int i=0;i<=m_nodes;i++)
            m_visited[i]=0;
    }


    vector<int> bfs(int source)
    {
        deque<int> q;

        vector<int> distances(m_nodes+5,-1);

        distances[source]=0;

        q.push_back(source);


        while(!q.empty())
        {
            int current = q.front();

            q.pop_front();

            for(auto it: m_adjList[current])
            {
                if(distances[it.first]==-1)
                {
                    distances[it.first]=1+distances[current];
                    q.push_back(it.first);
                }
            }

        }


        return distances;

    }

    void dfs(int node)
    {
        m_visited[node]=1;

        for(auto it:m_adjList[node])
        {
            if(m_visited[it.first]) continue;
            dfs(it.first);
        }
    }

    int getCC()
    {

        resetVisited();

        int ans=0;
        for(int i=1;i<=m_nodes;i++)
            if(!m_visited[i]) dfs(i),ans++;


        return ans;
    }



};


int main()
{

    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    int n,m,x,y,source;

    fread(buff,1,dim,stdin);

    read(n);
    read(m);
   /** read(source);

    //scanf("%d%d%d",&n,&m,&source);

    Graph G(n,0);


    for(int i=0;i<m;i++)
    {
        //scanf("%d%d",&x,&y);

        read(x);
        read(y);

        G.addEdge(x,y,0);
    }

    vector<int> solution=G.bfs(source);


    for(int i=1;i<=n;i++)
        printf("%d ",solution[i]);**/

    Graph G(n,0);

    for(int i=1;i<=m;i++)
    {
        read(x);
        read(y);

        G.addEdge(x,y,0);
        G.addEdge(y,x,0);
    }

    printf("%d\n",G.getCC());



    return 0;
}