Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.4 kB
0
Indexable
Never
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

class Graph{
	public:
        long num;
        vector < vector < long > > adj;
        Graph(int num){
            this->num = num;
            for (int i = 0; i < this->num; ++i){
                this->adj.push_back(vector < long > ());
            }
        }
        void addEdge(long u, long v){
            if (u < 0 || u >= this->num || v < 0 || v >= this->num){
                return;
            }
            this->adj.at(u).push_back(v);
        }

        /*void showgraph(){
            cout << "\n Graph Adjacency List ";
            for (int i = 0; i < this->num; ++i){
                cout << " \n [" << i+1 << "] :";
                // iterate edges of i node
                for (int j = 0; j < this->adj.at(i).size(); j++){
                    cout << "  " << this->adj.at(i).at(j)+1;
                }
            }
        }*/

        void dfs(bool visited[], long src){
            if (src < 0 || src >= this->num){
                // In case given invalid node
                return;
            }
            // Mark a current visited node
            visited[src] = true;
            long i = 0;
            // Execute edges of given src num
            while (i < this->adj.at(src).size()){
                if (visited[this->adj.at(src).at(i)] == false){
                    // When edge node not visiting, then perform DFS operation
                    this->dfs(visited, this->adj.at(src).at(i));
                }
                // Visit to next node
                i++;
            }
        }

        void subgraph_num(){
            bool visited[this->num];
            long result = 0;
            for (int i = 0; i < this->num; ++i){
                visited[i] = false;
            }
            for (int i = 0; i < this->num; ++i){////////////
                if (visited[i] == false){
                    result++;
                    this->dfs(visited, i);
                }
            }
            cout << result;
        }
};

int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);
    long n;
	cin>>n;
	Graph *g = new Graph(n);
	for(int i = 0 ; i < n-1 ; i++){
        long a,b;
        cin>>a>>b;
        g->addEdge(a-1,b-1);
    }
	//g->showgraph();
	g->subgraph_num();
	return 0;
}