数式を処理中: 100%

実装例

?
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
typedef vector< vector< int > > Graph;
inline void dfs(int idx, const Graph& graph, vector< bool >& used, vector< int >& order)
{
if(used[idx]) return;
used[idx] = true;
for(int i = 0; i < graph[idx].size(); i++) {
dfs(graph[idx][i], graph, used, order);
}
order.push_back(idx);
}
inline void rdfs(int idx, const Graph& rgraph, vector< int >& cmp, const int& cnt)
{
cmp[idx] = cnt;
for(int i = 0; i < rgraph[idx].size(); i++) {
if(cmp[rgraph[idx][i]] == -1) rdfs(rgraph[idx][i], rgraph, cmp, cnt);
}
}
size_t StronglyConnectedComponents(const Graph& graph, vector< int >& cmp)
{
size_t cnt = 0;
Graph rgraph(graph.size());
for(int i = 0; i < graph.size(); i++) {
for(int j = 0; j < graph[i].size(); j++) {
rgraph[graph[i][j]].push_back(i);
}
}
cmp.assign(graph.size(), -1);
vector< bool > used(graph.size(), false);
vector< int > order;
for(int i = 0; i < graph.size(); i++) {
dfs(i, graph, used, order);
}
reverse(order.begin(), order.end());
for(int i = 0; i < order.size(); i++) {
if(cmp[order[i]] == -1) rdfs( order[i], rgraph, cmp, cnt), cnt++;
}
return cnt;
}

問題例

# ソース 難易度
AOJ GRL_3 C - 強連結成分分解 -