ARC037 B - バウムテスト

概要

N頂点M辺の無向グラフの連結成分のうち、閉路を持たないものの個数をもとめよ。

制約

1 ≦ N ≦ 100
1 ≦ M ≦ N(N-1)/2

方針

各頂点でDFSを行い、DFS内で1度通った頂点にまた通ることがあれば閉路を持つと判定する。

感想

昔解いたやつですが、備忘のため記事にしました。

解答

Submission #1175993 - AtCoder Regular Contest 037

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
#define pb push_back
using namespace std;
 
#include <map>
#include <set>
#include <queue>
 
typedef long long ll;
typedef unsigned long long ull;
 
int n,m;
vint G[110];
bool used[110];
bool ok;
 
void dfs(int x, int p){
	used[x] = true;
	for(int w : G[x]){
		if(w == p) continue;
		if(!used[w]) dfs(w, x);
		else ok = false;
	}
}
 
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> n >> m;
 
	rep(i,m){
		int a, b;
		cin >> a >> b;
		G[a-1].pb(b-1);
		G[b-1].pb(a-1);
	}
 
	int ans = 0;
	rep(i,n){
		if(!used[i]){
			ok = true;
			dfs(i,-1);
			if(ok) ans++;
		}
	}
 
	cout << ans << endl;
}