[UVA][SCC、Tarjan算法] 11770 - Lighting Away
J |
Lighting Away Input: Standard Input Output: Standard Output |
|
Ronju is a night-guard at the “Lavish office buildings Ltd.” headquarters. The office has a large grass field in front of the building. So every day, when Ronju comes to duty at the evening, it is his duty to turn on all the lights in the field. However, given the large size of the field and the large number of lights, it is very tiring for him to walk to each and every individual light to turn it on.
So he has devised an ingenious plan – he will swap the switches for light-sensitive triggers. A local electronic store nearby sells these funny trigger switches at a very cheap price. Once installed at a light-post, it will automatically turn that light on whenever it can sense some other light lighting up nearby. So from now on, Ronju can just manually flip a few switches, and the light from those will trigger nearby sensors, which will in turn light up some more lights nearby, and so on, gradually lighting up the whole field.
Now Ronju wonders: how many switches does he have to flip manually for this?
Input
The input starts with an integer T, the number of test cases to follow. Each test case will start with two integers N (1 <= N <= 10000) and M (0 <= M <= 100000), where N is the number of lights in the field, and M more lines of input follows in this input case. Each of these extra M lines will have two integers a and b separated by a space, where 1 <= a, b <= N, indicating that if the light a lights up, it will trigger the light b to turn on as well (according to their distance, brightness, sensor sensitivity, orientation and other complicated factors). Finally, every test case in the input will be followed by a blank line.
Output
For each input test case, the output must be a single line of the format “Case k: c” where k is the case number starting with 1, and c is the minimum number of lights that Ronju must turn on manually before all the lights in the whole field gets lit up.
Sample Input Output for Sample Input
|
2 5 4 1 2 1 3 3 4 5 3
4 4 1 2 1 3 4 2 4 3
|
Case 1: 2 Case 2: 2
|
做法 : 跟 11504 - Dominos 一樣, 將 SCC 縮點, 找 indeg 為 0 的個數
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define maxN 10010
using namespace std;
vector<int> g[maxN];
int stk[maxN], stkIdx;
int visited[maxN], in_stk[maxN];
int vfind[maxN], findIdx;
int lead[maxN];
int scc(int nd) {
visited[nd] = in_stk[nd] = 1;
stk[++stkIdx] = nd;
vfind[nd] = ++findIdx;
int mn = vfind[nd];
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(!visited[*it]) {
mn = min(mn, scc(*it));
}
if(in_stk[*it]) {
mn = min(mn, vfind[*it]);
}
}
if(mn == vfind[nd]) {
do {
lead[stk[stkIdx]] = nd;
in_stk[stk[stkIdx]] = 0;
} while(stk[stkIdx--] != nd);
}
return mn;
}
int main() {
int n, m, t, x, y;
int i, cases = 0;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++) {
g[i].clear();
vfind[i] = visited[i] = in_stk[i] = 0;
lead[i] = i;
}
while(m--) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
}
for(i = 1; i <= n; i++) {
if(!visited[i]) {
findIdx = 0, stkIdx = -1;
scc(i);
}
}
int indeg[10005] = {};
for(i = 1; i <= n; i++) {
for(vector<int>::iterator it = g[i].begin();
it != g[i].end(); it++) {
if(lead[*it] != *it)
indeg[*it]++;
if(lead[i] != lead[*it])
indeg[lead[*it]]++;
}
}
int ans = 0;
for(i = 1; i <= n; i++)
if(!indeg[i] && lead[i] == i)
ans++;
printf("Case %d: %d\n", ++cases, ans);
}
return 0;
}