传送门:http://lightoj.com/volume_showproblem.php?problem=1034
1034 - Hit the Light Switches
Time Limit:2 second(s)
|
Memory Limit:32 MB
|
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
Input starts with an integerT (≤ 15), denoting the number of test cases.
Each case contains a blank line two integersN (1 ≤ N ≤ 10000)andM (0 ≤ M ≤ 105), whereNis the number of lights in the field, andMmore lines of input follows in this input
case. Each of these extraMlines will have two different integersaandbseparated by a space, where1 ≤ a, b ≤ N, indicating that if the lightalights up, it will trigger
the lightbto turn on as well (according to their distance, brightness, sensor sensitivity, orientation and other complicated factors).
Output
For each case, print the case number and 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
|
PROBLEM SETTER: SAMEE ZAHUR
SPECIAL THANKS: JANE ALAM JAN
题意:求一个有向图的最小点基,很裸。
思路:直接求出强连通+缩点,然后找入度为0的点即可。
代码:
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
/**
最小点基
**/
const int MAXN = 11111;
int low[MAXN],dfn[MAXN],belong[MAXN],deg[MAXN],ans,scc,t,n,m,depth;
vector<int> g[MAXN],gs[MAXN];
stack<int> s;
void init(){
for(int i=0;i<MAXN;i++)g[i].clear(),gs[i].clear();
memset(dfn,-1,sizeof(dfn));
memset(belong,-1,sizeof(belong));
memset(deg,0,sizeof(deg));
ans = scc = depth = 0 ;
while(!s.empty())s.pop();
}
void tarjan(int u){
low[u] = dfn[u] = depth++;
s.push(u);
for(int i=0;i<(int)g[u].size();i++){
int v = g[u][i];
if(dfn[v]==-1){
tarjan(v);
low[u] = min(low[u],low[v]);
}else if(belong[v]==-1){
low[u] = min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
int v;
do{
v = s.top();
belong[v] = scc;
s.pop();
}while(v!=u);
scc++;
}
}
void DFS(int u){
dfn[u] = 1;
for(int i=0;i<(int)g[u].size();i++){
int v = g[u][i];
if(belong[u]!=belong[v])deg[belong[v]]++;
if(!dfn[v])DFS(v);
}
}
void solve(){
for(int i=0;i<scc;i++)if(!deg[i])ans++;
}
int main(){
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
init();
scanf("%d%d",&n,&m);
while(m--){
int a,b;
scanf("%d%d",&a,&b);a--,b--;
g[a].push_back(b);
}
for(int i=0;i<n;i++)if(dfn[i]==-1)tarjan(i);
memset(dfn,0,sizeof(dfn));
for(int i=0;i<n;i++)if(!dfn[i])DFS(i);
solve();
printf("Case %d: %d\n",cas,ans);
}
return 0;
}
分享到:
相关推荐
LightOJ-已解决代码我所有的Light Online Judge的解决问题代码。
轻描淡写 像Codeforces编辑模式一样在lightoj上发表社论!
LightOJ-solutions
LightOJ
leetcode中国 数据结构和算法编码 议程 :balloon: 不是为了比赛,而是为了训练和兴趣。 Python3 你可以在这里找到我的 LeetCode 解决方案:(等待打开) ...LightOJ 1012 --- dfs transform 13. HDU 1495 --- compl
E-Olymp-ECNU在线法官-Facebook黑客杯-FZU在线法官-Google Code Jam(新)-Google Kick Start-HackerEarth-HackerRank-HDU在线法官-HIT在线法官-hihoCoder-Hrbust Online法官-ICPC实时存档-Jutge-Kattis-LightOJ-MSK...
问题教程:一个包含有关LightOJ问题的教程的存储库
leetcode 2 和 c 动态规划 动态规划相关问题的解答。 这些问题来自各种在线评委,包括 、 、 等。 解决方案是用 C++ 编码的。 —— —— —— —— —— —— —— —— —— —— —— —— ...——
光OJ 收集我在发现的一些问题的解决方案
已解决的编程问题 Online Judges 这个存储库包含我解决的各种在线法官的编程问题的解决方案,即 UVa、Topcoder、Codeforces、Hackerrank、LightOj、Spoj、Project Euler 等。
race_words = [“后缀数组”,“前缀特里”,“动态编程”,“竞赛”,“ codeforces”,“编程”,“竞争性编程”,“算法”,“数据结构”,“ codeforces”,“ light oj”,“ lightoj”,“ spoj”,“堆栈”,...
这是乔杜里医学博士。 伊斯玛姆·拉赫曼(Ishmam Rahman) :closed_mailbox_with_raised_flag: 联络我: ... LightOJ: ://lightoj.com/user/ishmam64 脸书: : 目标:使自己在新技术的海洋中立足,在这里我可
描述在这里,您可以从uva,lightoj,spoj,timus等不同的在线法官那里找到我解决的问题。
开心农场java源码AA Noman Ansary 你好呀! 我的名字是AA Noman Ansary 。 但我更喜欢被称为Showrav...问题解决:LightOJ。 代码部队。 蒂姆斯。 紫外线。 成就 以下是我的一些显著成就: BRAC 大学副校长证书。 (2019)
这个仓库是关于什么的 创建该存储库是为了组织与数据结构和算法有关的问题的解决方案。 并且,如果可能的话,为学习与数据结构和算法有关的各种概念提供一种更简单的方法。 以下评委使用的问题 ...
测试程序TestProgram 是针对竞争性编程程序(即 Codeforces、lightOJ、OmegaUp 等)的专用测试工具。 当我们解决问题时,我们必须非常小心,并致力于解决所有可能的情况。 我们的解决方案在登顶前正确解决的测试用例...
problemSolving