https://www.acmicpc.net/problem/2252


뭐의 앞에 뭐가 오고, 뭐의 앞엔 뭐가 온다 이런 형태로 정보가 주어지면 위상 정렬을 수행한다.



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
 
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int n, m, ind[32002];
vector<int> v[32002];
queue<int> q;
void tpgSort() {
    for (int i = 1; i <= n; i++) { //indegree 0인거 큐에 넣고 시작
        if (ind[i] == 0) q.push(i);
    }
 
    for (int i = 0; i < n; i++) { // 노드의 개수보다 더 많이 돌면 사이클
        if (q.empty()) cout << "cycle occured\n";
 
        int cur = q.front(); q.pop();
        cout << cur << ' '; //노드 삭제
 
        
        for (int i = 0; i < v[cur].size(); i++) {
            ind[v[cur][i]]--; //삭제된 노드와 연결된 간선 제거
            if (ind[v[cur][i]] == 0) q.push(v[cur][i]);
        }
 
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
 
    while (m--) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }
    tpgSort();
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2056 작업 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14

https://www.acmicpc.net/problem/4195


유니온 파인드를 단순히 적용하면 TLE를 맞는 문제이다.


따라서 배열에 지속적으로 그룹의 크기를 저장해줘야 하는데, 따라서 일관성을 가지도록 union함수를 구현해줘야한다.


무조건 작은 값이 부모가 되도록 하는 것이다.



처음에는 단순하게 주석 처리된 부분으로 제출해서 TLE를 맞았다. 가장 단순하게 할 수 있는 해결법이, 쿼리를 진행하기 전에,


모든 원소에 대해서 부모 검색을 다시 수행해서 제대로 된 부모들을 찾아두는 것인데, 이 방법을 사용할 수 없다.




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
70
71
72
73
74
75
76
77
#include<iostream>
#include<map> //찾는 게 없으면 0반환
#include<string>
#include<algorithm>
using namespace std;
map<string, int> mp;
 
int r[200002], fcnt[200002];
 
int getParent(int a) {
    if (r[a] == a) return r[a];
    else
        return r[a] = getParent(r[a]);
}
int join(int a, int b) {
    
    a = getParent(a);
    b = getParent(b);
    if (a < b) {
        r[b] = a;
        fcnt[a] += fcnt[b];
        fcnt[b] = 1;
        return fcnt[a];
    }
    else if (a > b) {
        r[a] = b;
        fcnt[b] += fcnt[a];
        fcnt[a] = 1;
        return fcnt[b];
    }
    return fcnt[b];
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int idx = 0;
        for (int i = 0; i < 2 * n; i++) {
            r[i] = i;
            fcnt[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            string fir, sec;
            cin >> fir >> sec;
 
            if (mp.count(fir) == 0) {
                mp.insert({ fir, idx });
                idx++;
            }
            if (mp.count(sec) == 0) {
                mp.insert({ sec, idx });
                idx++;
            }
            
            cout << join(mp[fir], mp[sec]) << '\n';
            
            //for (int i = 1; i < idx; i++) getParent(i);
 
            //int cnt = 0;
            //for (int i = 0; i < idx; i++)
            //    if (r[i] == r[mp[fir]])
            //        cnt++;
            //cout << cnt << '\n';
        
        }
        mp.clear();
        
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1766 문제집 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14

https://www.acmicpc.net/problem/1717


유니온파인드를 활용하는 문제이다.


주의할 점은, 항상 특정 노드의 최상위 부모가, 업데이트가 되어있지 않을 수 있다는 생각을 하고, 구현을 해야한다는 것이다.


따라서 최상위 부모를 찾으러 올라갈 때도, 항상 getParent 함수를 호출하면서 올라간다.


마찬가지로 union연산을 할 때에도, a혹은 b의 최상위 부모가 제대로 갱신이 되어있지 않을 수 있기 때문에 마찬가지로 갱신을 하면서 찾아준다.


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
#include<iostream>
using namespace std;
int r[1000002], n;
 
int getParent(int a) {// 마찬가지로 갱신하면서 찾으러 올라감
    if (r[a] == a) return r[a];
    else return r[a] = getParent(r[a]);
}
 
void join(int a, int b) { //갱신하면서
    r[getParent(a)] = getParent(b); //a의 부모를 b의 부모로 update 한다
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m;
    cin >> n >> m;
    
    for (int i = 0; i <= n; i++)
        r[i] = i;
 
    for (int i = 0, cmd, a, b; i < m; i++) {
        cin >> cmd >> a >> b;
        if (cmd == 0)
            join(a, b);
        else if (cmd == 1) {
            //for (int i = 0; i <= n; i++) getParent(i);
            int pa = getParent(a);
            int pb = getParent(b);
            if (pa == pb) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14

https://www.acmicpc.net/problem/10451


그래프 정보를 배열로 받아주고, DFS를 돌려주면 된다.


DFS를 실행할 때, 방문한 지점을 다시 방문하는 것이 base condition이므로, DFS가 끝날 때 마다 사이클의 개수가 하나씩 늘어난다.


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
#include<iostream>
#include<vector>
using namespace std;
int v[1002];
bool vis[1002];
 
void dfs(int cur) {
    if (vis[cur]) return; //이미 방문한 곳을 재방문 했다는 건 사이클이라는 뜻
 
    vis[cur] = true;
    int next = v[cur];
    dfs(next);
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        
        for (int i = 1; i <= n; i++) 
            cin >> v[i];
        
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && v[i] != 0) {
                cnt++;
                dfs(i);
            }
        }
        cout << cnt << '\n';
 
        for (int i = 1; i <= n; i++) 
            vis[i] = false;
        
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14

기본이 max이고 less<>라고 외우면 되겠다.


greater 을 사용하려면 functional 헤더를 인클루드 시켜줘야한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <queue>
using namespace std;
 
struct a{
    int start;
    int en;
    int value;
};
 
bool operator<(a t, a u){
    return t.value < u.value;
}
 
priority_queue<a> pq;
 

cs



구조체와 함께 사용한다면 위와 같이 < 연산자를 오버로딩해서 사용하는데, value가 큰 것부터 나온다.


value가 작은 것부터 나오게 하려면, 12번째 줄의 <를 >로 바꿔주면 된다.



저작자표시 비영리 변경금지

'Programming Language > C++' 카테고리의 다른 글

vector upper_bound, lower_bound 사용 (C++)  (0) 2019.09.01
string 대소문자 변환  (0) 2019.08.25
(C++) abs 함수의 사용  (0) 2019.08.07
(C++) list STL 출력 및 iterator  (0) 2019.08.04
next_permutation  (0) 2019.07.21

+ Recent posts

티스토리툴바