Untitled
unknown
plain_text
3 years ago
2.4 kB
1
Indexable
#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; }
Editor is loading...