문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4393
오염된 물을 정화하기 위해서 단방향 그래프에서 0번 정점에서 나오는 정화제를 x개의 간선을 추가하여 모든 정점에 뿌려야할 때 연결해야하는 간선 x개의 최솟값을 구하는 문제이다.
이 문제는 정점들을 scc로 묶어준다음 위상정렬을 통하여 해결가능하다.
즉 0번 정점을 포함한 scc를 제외한 indegree가 0인 scc의 개수를 출력해주면 된다.
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 <algorithm> #include <cstring> #include <vector> #include <stack> #include <queue> using namespace std; int n, m, x, y, in[1010], r, disc[1010], scc[1010], sccc, c; vector<vector<int>> vt; vector<pair<int, int>> edge; vector<vector<int>> svt; stack<int> st; int dfs(int here) { disc[here] = ++c; int ret = disc[here]; st.push(here); for (auto next : vt[here]) { if (!disc[next]) ret = min(ret, dfs(next)); else if (!scc[next]) ret = min(ret, disc[next]); } if (ret == disc[here]) { sccc++; while (1) { int h = st.top(); st.pop(); scc[h] = sccc; if (h == here)break; } } return ret; } int main(){ while (scanf("%d%d", &n, &m) != EOF) { memset(in, 0, sizeof(in)); memset(disc, 0, sizeof(disc)); memset(scc, 0, sizeof(scc)); edge.assign(m + 1, { 0,0 }); vt.clear(); vt.resize(n + 1); c = sccc = r = 0; for (int i = 0; i < m; i++) { scanf("%d%d", &edge[i].first, &edge[i].second); vt[edge[i].first].push_back(edge[i].second); } for (int i = 0; i <= n; i++) if (!disc[i])dfs(i); for (int i = 0; i < m; i++) { if (scc[edge[i].first] == scc[edge[i].second])continue; in[scc[edge[i].second]]++; } for (int i = 1; i <= sccc; i++) if (i != scc[0] && !in[i])r++; printf("%d\n", r); } return 0; } | cs |
'알고리즘 관련 > UVaOJ' 카테고리의 다른 글
UVaOJ)12159 Gun Fight (0) | 2017.06.27 |
---|---|
UVaOJ)12878 Flowery Trails (0) | 2017.06.23 |
UVaOJ)10968 KuPellaKeS (0) | 2017.06.20 |
UVaOJ)11751 Installing Diagnostic Software (0) | 2017.06.19 |
UVaOJ)12460 Careful teacher (0) | 2017.06.17 |