'Programming Problems/Graph'에 해당되는 글 7건

Programming Problems/Graph

셋 전부 합치기 Q

본인이 테일 노드이거나, 테일 노드를 가리키거나, 테일 노드로 이어지는 노드를 가리키면 good 노드이다.

모든 노드가 good이 되기 위한 최소 포인터 변경 횟수는?


아무래도 union_set 문제인 것 같다. 구체적인 구현으로는,

본인의 종결점을 찾는다. 그것이 tail이 아니면 그것을 테일로 가리킨다.

모든 노드에 대해 수행한다. 물론 visited를 써 가면서 수행하자. 그렇게 하면 O(N) 수행시간을 얻는다..!! DFS


>> 횟수가 곧 최소 횟수이다!!


vector<bool> visited;


for(int i = 0 ; i < graph.size() ; i++){

if(visited[i]!=false){

// not containing node 1, need to move pointer

if(!goDFS) count++;

}

}


return count;



https://www.careercup.com/question?id=5840928073842688

Programming Problems/Graph

N개의 노드에 대해 acyclic이 되는 최대 엣지의 갯수는(방향,비방향)

비방향 그래프에서는 최대 V-1 개의 엣지가 가능하다. spanning tree이다. 그 이상 연결하면 반드시 사이클이 생긴다.

방향 그래프에서는 Topological sort를 고려한다고 생각해 보면 맨 앞에서는 V-1개 , V-2 ... 1 의 총합은 V(V-1)/2 개이다.

Programming Problems/Graph

사이클 없는 그래프에서 각 점에의 최대 트래픽 찾기 Q

각 점에서의 최대 트래픽을 구해보자.


ex)


1   2

  5

4   3


의 경우


1 14

2 13

3 12

4 11

5 4가 나와야 한다.


모든 점에서 nearby 점의 값들 중 최대값을 고려하는 듯 한데 이걸 preprocessing으로 풀어서 O(N) 을 만든 것으로 보인다. 그냥 나이브하게 구하면 O(N^2) 알골이 된다.

// preprocess your input graph to the following structure
// node -> hash set of neighbors
// hash set to enable amortized O(1) deletions 
vector<unordered_set<int>> topology(n);
vector<int> metadata(n); // contains the population count
vector<int> current_leaf_set;
int global_sum = 0;
for each node id i in topology{
    if(topology[i].size() == 1 ) current_leaf_set.push_back(i);
	global_sum += metadata[i];
}
int i = 0;
vector<int> sum(n), max(n); // initialize them to zero
while(i < current_leaf_set.size()){
        int node_id = current_leaf_set[i++];
	std::cout << node_id << " : " << (std::max( max[node_id], global_sum - metadata[node_id] - sum[node_id] )) << "\n";
	if( topology[node_id].size() == 0 ) continue; // Thanks @helloru
        int next_node = *(topology[node_id].begin()); // will only have one neighbor
	sum[next_node] += ( metadata[node_id] + sum[node_id]);
	max[next_node] = std::max( max[next_node], ( metadata[node_id] + sum[node_id]) );
	topology[next_node].erase(node_id);
	if( topology[next_node].size() == 1 ) current_leaf_set.push_back(next_node);
}



https://www.careercup.com/question?id=5695046734053376

Programming Problems/Graph

배열 스왑해서 정렬하기 (BFS 응용)

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include "stdafx.h"
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
 
using namespace std;
 
void makeBFS(int n,map<vector<int>,int> & data) {
    // make buffere queue and starting point
    vector<int> perm(n);
    for (int i = 0; i < n; i++) {
        perm[i] = i;
    }
    int flag = 0;
    long long count = 0;
    queue<pair<vector<int>,int>> buffer;
    buffer.push(pair<vector<int>,int>(perm,0));
    data.insert(pair<vector<int>int>(perm, 0));
    while (buffer.size() != 0) {
        count++;
        if (count % 500 == 0cout << "running at " << count << endl;
        vector<int> curr = buffer.front().first;
        int dis = buffer.front().second;
        buffer.pop();
        // make all combinations and put in map
        vector<int> tmp;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                tmp = curr;
                reverse(tmp.begin() + i, tmp.begin() + j + 1);
                if (data.find(tmp) == data.end()) {
                    if (flag < dis) {
                        cout << "current at " << dis << endl;
                        flag++;
                    }
                    data.insert(pair<vector<int>int>(tmp, dis + 1));
                    buffer.push(pair<vector<int>int>(tmp, dis + 1));
                }
            }
        }
    }
}
 
void swap(int & a, int & b) {
    int tmp = a;
    a = b;
    b = tmp;
}
 
int findminswaps(vector<int> & data) {
    map<vector<int>int> buf;
    // rescale data to 0 ... n-1
    for (int i = 0; i < data.size(); i++) {
        int smaller = 0;
        for (int j = 0; j < data.size(); j++) {
            if (data[i] > data[j]) smaller++;
        }
        data[i] = smaller;
    }
    for (int x : data) cout << x << " ";
    cout << endl;
    // make BFS
    makeBFS(data.size(), buf);
    // find min distance
    auto it = buf.find(data);
    if (it == buf.end()) return -9999;
    return it->second;
}
 
map<vector<int>int> toSort;
 
void precalc(int n) {
    vector<int> perm(n);
    for (int i = 0; i < n; ++i) {
        perm[i];
    }
    queue<vector<int>> q;
    q.push(perm);
    toSort[perm] = 0;
    int count = 0;
    while (!q.empty()) {
        count++;
        if (count % 500 == 0cout << "count at : " << count << endl;
        vector<int> here = q.front();
        q.pop();
        int cost = toSort[here];
        for (int i = 0; i < n; ++i) {
            for (int j = i + 2; j <= n; j++) {
                reverse(here.begin() + i, here.begin() + j);
                if (toSort.count(here)==0) {
                    toSort[here] = cost + 1;
                    q.push(here);
                }
                reverse(here.begin() + i, here.begin() + j);
            }
        }
    }
}
 
int solve(const vector<int> & perm) {
    int n = perm.size();
    vector<int> fixed(n);
    for (int i = 0; i < n; ++i) {
        int smaller = 0;
        for (int j = 0; j < n; ++j) {
            if (perm[j] < perm[i])
                ++smaller;
        }
        fixed[i] = smaller;
    }
    return toSort[fixed];
}
 
int main() {
    map<vector<int>int> tmp;
    vector<int> v1 = { 1,2,3,4,8,7,6,5 };
    precalc(8);
    cout << solve(v1) << endl;
    //cout << findminswaps(v1) << endl;
    while(1){}
    return 0;
}
cs


Programming Problems/Graph

끝말잇기 문제 (오일러 경로)

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include "stdafx.h"
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <string>
 
using namespace std;
 
void DFS(vector<vector<vector<string>>> & graph, vector<bool> &visited, int target) {
    visited[target] = true;
    // visit adjacent nodes
    for (int i = 0; i < 26; i++) {
        if (graph[target][i].size() != 0 && visited[i] == false) {
            DFS(graph, visited, i);
        }
    }
}
 
void eulerpath(vector<vector<vector<string>>> & graph, vector<string> & res, int target) {
    // go through adjacent nodes
    stack<string> buffer;
    for (int i = 0; i < 26; i++) {
        while (graph[target][i].size() != 0) {
            buffer.push(graph[target][i][graph[target][i].size() - 1]);
            graph[target][i].pop_back();
            eulerpath(graph, res, i);
        }
    }
    while (buffer.size() != 0) {
        res.push_back(buffer.top());
        buffer.pop();
    }
}
 
void tictactoe(vector<string> & data) {
    // make graph
    vector<vector<vector<string>>> graph(26vector<vector<string>>(26vector<string>()));
    vector<int> inbound(260);
    vector<int> outbound(260);
    for (int i = 0; i < data.size(); i++) {
        int from = data[i][0]-'a';
        int to = data[i][data[i].size() - 1]-'a';
        graph[from][to].push_back(data[i]);
        outbound[from]++;
        inbound[to]++;
    }
 
    // check if graph is seperated
    vector<bool> visited(26false);
    int count = 0;
    int point = 0;
    for (int i = 0; i < 26; i++) {
        if (inbound[i]!=0&&outbound[i]!=0&&visited[i] == false) {
            point = i;
            count++;
            DFS(graph, visited, i);
        }
    }
    if (count != 1) {
        cout << "IMPOSSIBLE1" << endl;
        return;
    }
 
    // check if trail or cycle is possible
    int sc = 0;
    int start = 0;
    int lc = 0;
    int end = 0;
    for (int i = 0; i < 26; i++) {
        if (outbound[i] == inbound[i]) {
 
        }
        else if (outbound[i] == inbound[i] + 1) {
            lc++;
            start = i;
        }
        else if (outbound[i] + 1 == inbound[i]) {
            sc++;
            end = i;
        }
        else {
            cout << "IMPOSSIBLE2" << endl;
            return;
        }
    }
    // if lc or sc not balanced, return impossible
    vector<string> res;
    if (lc == 0 && sc == 0) {
        // euler cycle. start anywhere
        eulerpath(graph, res, point);
    }
    else if (lc == 1 && sc == 1) {
        // euler trail, start from start element
        graph[start][end].push_back("eraseme");
        eulerpath(graph, res, start);
        // erase eraseme
        for (int i = 0; i < res.size(); i++) {
            if (res[i] == "eraseme") {
                res.erase(res.begin() + i);
                break;
            }
        }
    }
    else {
        // not possible
        cout << "IMPOSSIBLE3" << endl;
        return;
    }
    reverse(res.begin(), res.end());
    for (string x : res) {
        cout << x << endl;
    }
}
 
int main() {
    vector<string> data = { "dog","god","dragon","need" };
    tictactoe(data);
    while(1){}
    return 0;
}
cs


Programming Problems/Graph

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
bool findpath(vector<vector<int>> & board) {
    // make graph
    vector<vector<int>> graph(board.size()*board[0].size(), vector<int>());
    int count = 0;
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) {
            // connect adjacent nodes
            vector<vector<int>> dir = { {-1,0},{1,0},{0,1},{0,-1} };
            for (int k = 0; k < 4; k++) {
                if (i + dir[k][0] >= 0 && i + dir[k][0] < board.size() && j + dir[k][1] >= 0 && j + dir[k][1] <= board[0].size() && board[i + dir[k][0]][j + dir[k][1]] != -1) {
                    if (k >= 2) addedge(graph, count, count + dir[k][2]);
                    else addedge(graph, count, count + board[0].size()*dir[k][1]);
                }
            }
            count++;
        }
    }
    // do DFS
    vector<bool> visited(graph.size(), false);
    stack<int> buffer;
    buffer.push(0);
    while (buffer.size() != 0) {
        int curr = buffer.top();
        buffer.pop();
        visited[curr] = true;
        for (int i = 0; i < graph[curr].size(); i++) {
            // return when end met
            if (graph[curr][i] == graph.size() - 1) return true;
            
            if (visited[graph[curr][i]] == false) {
                buffer.push(graph[curr][i]);
            }
        }
    }
    return false;
}
cs


Programming Problems/Graph

DAG topological sort 응용문제

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
void IDFS(vector<vector<int>> & graph, vector<bool> & visited, stack<int> & res, int target) {
    visited[target] = true;
    for (int i = 0; i < graph[target].size(); i++) {
        if (visited[graph[target][i]] == false) {
            IDFS(graph, visited, res, graph[target][i]);
        }
    }
    res.push(target);
}
 
vector<char> language(vector<string> & data) {
    // make char vector
    vector<vector<int>> graph(26, vector<int>());
    // parse data to fill char graph
    for (int i = 0; i < data.size() - 1; i++) {
        // compare strings to find char priority
        int curr = 0;
        while (curr < data[i].size() && curr < data[i + 1].size()) {
            if (data[i][curr] == data[i + 1][curr]) curr++;
            else {
                graph[data[i][curr] - 'a'].push_back(data[i + 1][curr] - 'a');
                break;
            }
        }
    }
    // do topological sort
    stack<int> res;
    vector<bool> visited(26, false);
    for (int i = 0; i < 26; i++) {
        if (visited[i] == false) {
            IDFS(graph, visited, res, i);
        }
    }
    vector<char> ret;
    while (res.size() != 0) {
        ret.push_back(res.top() + 'a');
        res.pop();
    }
    // validate cycle
    for (int i = 0; i < 26; i++) {
        for (int j = i + 1; j < 26; j++) {
            for (int k = 0; k < graph[ret[j] - 'a'].size(); k++) {
                if (graph[ret[j] - 'a'][k] == ret[i] - 'a') return vector<char>(1, 0);
            }
        }
    }
    return ret;
}
cs