How We Coding

[4803] 트리

BOJ/Tree2018. 5. 21. 01:58

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


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

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


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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;
}
 
cs



<예전코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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;
}
 
 
cs


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

'BOJ > Tree' 카테고리의 다른 글

[11725] 트리의 부모 찾기  (0) 2018.05.20
[1991] 트리 순회  (0) 2018.05.20

[11725] 트리의 부모 찾기

BOJ/Tree2018. 5. 20. 01:52

[11725] 트리의 부모 찾기 : http://boj.kr/11725


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    vector<int> v[100001];
    for(int i=1; i<n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    vector<int> p(n+1, 0);
    
    queue<int> q;
    q.push(1);
    p[1] = -1;
 
    while(!q.empty()) {
        int parent = q.front(); q.pop();
 
        for(int i=0; i<v[parent].size(); i++) {
            int child = v[parent][i];
            if(!p[child]) {
                q.push(child); 
                p[child] = parent;
            }
        }
    }
 
    for(int i=2; i<=n; i++)
        printf("%d\n", p[i]);
 
    return 0;
}
cs


>> 부모를 찾지 못했다면 큐에 넣고 부모 저장. BFS.

'BOJ > Tree' 카테고리의 다른 글

[4803] 트리  (0) 2018.05.21
[1991] 트리 순회  (0) 2018.05.20

[1991] 트리 순회

BOJ/Tree2018. 5. 20. 01:19

[1991] 트리 순회 : http://boj.kr/1991


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
#include <stdio.h>
 
char tree[26][2];
 
void pre(int root)
{
    if(root == '.') return ;
    printf("%c", root+'A');
    pre(tree[root][0]);
    pre(tree[root][1]);
}
 
void in(int root)
{
    if(root == '.') return ;
    in(tree[root][0]);
    printf("%c", root+'A');
    in(tree[root][1]);
}
 
void post(int root)
{
    if(root == '.') return ;
    post(tree[root][0]);
    post(tree[root][1]);
    printf("%c", root+'A');
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    while(n--) {
        char p, lc, rc;
        scanf(" %c %c %c", &p, &lc, &rc);
        tree[p-'A'][0] = lc == '.' ? lc : lc-'A';
        tree[p-'A'][1] = rc == '.' ? rc : rc-'A';
    }
 
    pre(0); puts("");
    in(0); puts("");
    post(0); puts("");
    
    return 0;
}
cs

'BOJ > Tree' 카테고리의 다른 글

[4803] 트리  (0) 2018.05.21
[11725] 트리의 부모 찾기  (0) 2018.05.20

티스토리툴바