LightOJ 1300 Odd Personality
Odd Personality
This problem will be judged on LightOJ. Original ID: 1300
64-bit integer IO format: %lld Java class name: Main
Being an odd person, Jim always liked odd numbers. One day he was visiting his home town which consists of n places and m bidirectional roads. A road always connects two different places and there is at most one road between two places. The places are numbered from 0 to n-1.
Jim wants to find a tour which starts from a place p and each time it goes to a new road and finally at last step it returns back to p. As Jim likes odd numbers, he wants the length of the tour to be odd. And the length of a tour is defined by the number of roads used in the tour.
For the city map given above, 0 - 1 - 2 - 0 is such a tour, so, 0 is one of the results, since from 0, a tour of odd length is found, similarly, 1 - 2 - 0 - 1 is also a valid tour. But 3 - 2 - 0 - 1 - 2 - 3 is not. Since the road 2 - 3 is used twice. Now given the city map, Jim wants to find the number of places where he can start his journey for such a tour. As you are the best programmer in town, he asks you for help. Jim can use a place more than once, but a road can be visited at most once in the tour.
Input
Input starts with an integer T (≤ 30), denoting the number of test cases.
Each case starts with a blank line. The next line contains two integers: n (3 ≤ n ≤ 10000) and m (0 ≤ m ≤ 20000). Each of the next m lines contains two integers u v (0 ≤ u, v < n, u ≠ v) meaning that there is a bidirectional road between place u and v. The input follows the above constraints. And no road is reported more than once.
Output
For each case, print the case number and the total number places where Jim can start his journey.
Sample Input
1
6 6
0 1
1 2
2 0
3 2
3 4
3 5
Sample Output
Case 1: 3
Source
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
struct arc {
int to,next;
arc(int x = ,int y = -) {
to = x;
next = y;
}
} e[maxn<<];
int head[maxn],dfn[maxn],low[maxn],color[maxn];
int tot,idx,cnt,n,m,flag,ans;
bool b[maxn];
void add(int u,int v) {
e[tot] = arc(v,head[u]);
head[u] = tot++;
}
void tarjan(int u,int fa) {
dfn[u] = low[u] = ++idx;
for(int i = head[u]; ~i; i = e[i].next) {
if(!dfn[e[i].to]) {
tarjan(e[i].to,u);
low[u] = min(low[u],low[e[i].to]);
if(low[e[i].to] > dfn[u]) b[i] = b[i^] = true;
} else if(e[i].to != fa) low[u] = min(low[u],dfn[e[i].to]);
}
}
void dfs(int u,int s) {
color[u] = s;
cnt++;
for(int i = head[u]; ~i; i = e[i].next) {
if(b[i]) continue;
if(color[e[i].to] && color[e[i].to] == color[u]) flag = ;
else if(color[e[i].to] == ) dfs(e[i].to,-s);
}
}
int main() {
int T,cs = ,u,v;
scanf("%d",&T);
while(T--) {
scanf("%d %d",&n,&m);
memset(head,-,sizeof(head));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(color,,sizeof(color));
memset(b,false,sizeof(b));
idx = ;
for(int i = tot = ; i < m; ++i) {
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
for(int i = ans = ; i < n; ++i)
if(!dfn[i]) tarjan(i,-);
for(int i = ; i < n; ++i)
if(color[i] == ) {
flag = cnt = ;
dfs(i,);
if(flag) ans += cnt;
}
printf("Case %d: %d\n",cs++,ans);
}
return ;
}
最新文章
- 周末聊聊IT人员的人脉观:关于帮妹子找兼职有感
- rqnoj378 约会计划
- ASP.NET MVC 多语言实现——URL路由
- Unsafe与CAS
- DDD领域驱动设计之领域基础设施层
- RecyclerView,CardView导入和使用(Demo)
- 全键盘Vimium快捷键学习记录
- android命令安装apk时报错:INSTALL_FAILED_CPU_ABI_INCOMPATIBLE
- memcached增删改查
- file与 byte[] 互转
- 从ramdisk根文件系统启动Linux成功
- SharePoint 2010 母版页定制小思路介绍
- BaseAdapter导致notifyDataSetChanged()无效的四个原因及处理方法
- hdu5696 区间的价值
- Linux-RED HAT6.8扩容
- NOIP2017游记
- 基于物理规则的渲染(PBR)
- StrokePlus常用脚本
- ROSETTA使用技巧随笔--RosettaLigand Docking
- 命名空间“Microsoft.Office.Interop”中不存在类型或命名空间名称“Excel”。是否缺少程序集引用 的另一种解决方案