Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <cstdlib>
- using namespace std;
- int n;
- vector < vector<int> > g;
- vector<int> cl;
- bool dfs (int v, int s) {
- cl[v] = 1;
- for (size_t i = 0; i < g[v].size(); i++) {
- int to = g[v][i];
- if (cl[to] == 0 && to != v && to != s) {
- if (dfs (to, v)) return true;
- }
- else if (cl[to] == 1 && to != v && to != s) {
- return true;
- }
- }
- cl[v] = 2;
- return false;
- }
- int main() {
- int i, k = 0, m;
- cin >>n >>m;
- g.assign(n, vector <int>());
- cl.assign(n, 0);
- for(i = 0; i < m; i++){
- int x, y;
- cin >>x >>y;
- x--;
- y--;
- g[x].push_back(y);
- g[y].push_back(x);
- //cout <<g[x] <<' ' <<g[y] <<endl;
- }
- for (int i = 0; i < n; i++){
- if(cl[i] == 0){
- if (!dfs (i, -1)){
- k++;
- }
- }
- }
- if(k > 1){
- cout <<"A forest of " <<k <<" trees.";
- } else {
- if(k == 1){
- cout <<"There is one tree.";
- } else {
- cout <<"No trees.";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement