[4803] 트리

[4803] 트리 : http://boj.kr/4803

- 정점의 갯수를 세고, 간선의 갯수를 센다.

- 트리는 정점의 갯수-1 이 간선의 갯수라는 성질을 만족한다.

<소스코드>

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
 
int n, m;
bool visited[501];
bool check[501];
 
int dfsV(vector<int> v[], int s)
{
    int ret = 1;
    visited[s] = 1;
    for(int i=0; i<v[s].size(); i++) {
        int next = v[s][i];
        if(!visited[next])
            ret += dfsV(v, next);
    }
    return ret;
}
 
int dfsE(vector<int> v[], int s)
{
    int ret=v[s].size();
    check[s] = 1;
    for(int i=0; i<v[s].size(); i++) {
        int next = v[s][i];
        if(!check[next])
            ret += dfsE(v, next);
    }
    return ret;
}
 
int main()
{
    int tc=0;
    while(1) {
        int ans=0;
 
        scanf("%d%d", &n, &m);
        if(!n && !m) break;
 
        vector<int> v[501];
        while(m--) {
            int a, b;
            scanf("%d%d", &a, &b);
            v[a].push_back(b);
            v[b].push_back(a);
        }
        
        memset(visited, 0, sizeof(visited));
        memset(check, 0, sizeof(check));
        for(int i=1; i<=n; i++) {
            if(!visited[i]) {
                int vertex = dfsV(v, i);
                int edge = dfsE(v, i);
                if(vertex-1 == edge/2)
                    ans++;
            }
        }
        tc++;
        printf("Case %d: ", tc);
        if(ans == 0) puts("No trees.");
        else if(ans == 1) puts("There is one tree.");
        else printf("A forest of %d trees.\n", ans);
    }
    return 0;
}
 

<예전코드>

#include <cstdio>
#include <vector>
using namespace std;
 
int v, e;
 
void dfs(vector<int> g[], bool visited[], int cur) 
{
    visited[cur] = true;
    v++;
 
    for(int i=0; i<g[cur].size(); i++) {
        int next = g[cur][i];
        e++;
        if(!visited[next]) {
            dfs(g, visited, next);
        }
    }
}
 
int main()
{
    int tc=1;
 
    while(1) {
        int n, m;
        scanf("%d %d", &n, &m);
 
        if(!n && !m) break;
        
        vector<int> g[501];
        while(m--) {
            int a, b;
            scanf("%d %d", &a, &b);
 
            g[a].push_back(b);
            g[b].push_back(a);
        }
        
        int ans=0;
        bool visited[501]={0};
        for(int i=1; i<=n; i++) {
            if(!visited[i]) {
                v = e = 0;
                dfs(g, visited, i);
                
                if(v-1 == e/2) ans++;
            }
        }
        printf("Case %d: ", tc++);
        if(!ans) puts("No trees.");
        else ans > 1 ? printf("A forest of %d trees.\n", ans) : puts("There is one tree.");
    }
 
    return 0;
}
 
 

>> dfs 를 한번만 호출해서 정점의 수와 간선의 수를 카운트했다.