NC50402. 网络
描述
输入描述
输入文件包括若干组测试数据。
每一组是一个网络，每一组测试数据的第一行是地点的总数量N。每组接下来最多有N行包括一个数字表示一个地点和与它相连接的地点的数字。最多N行可以完全描述整个网络，比如，网络中每个直接连接的两个地点被至少一行包括。一行内的所有数字都要用空格隔开。每组数据需要用单独的一个0结束。最后的块只有一行即N=0。
输出描述
输出除了最后一组，其他每一组的灾区的数量，每个块用一行输出。
示例1
输入:
5 5 1 2 3 4 0 6 2 1 3 5 4 6 2 0 0
输出:
1 2
Java 解法, 执行用时: 336ms, 内存消耗: 19780K, 提交时间: 2021-09-21 16:10:24
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String args[]){
new Thread(null, () -> new Main().solve(), "1", (1 << 30)).start();
}
Scanner in;
PrintWriter out;
public void solve(){
in = new Scanner(System.in);
out = new PrintWriter(System.out);
go();
}
int s[];
int ll[];
int rr[];
int setv[];
// void build(int id,int left,int right){
// if(left==right){
// s[id] = 1;
// ll[id] = rr[id] = wt[pt[left]];
// return;
// }
// int mid = (left+right)/2;
// build(id*2,left,mid);
// build(id*2+1,mid+1,right);
// s[id] = s[id*2] + s[id*2+1];
// if(rr[id*2]==ll[id*2+1]){
// s[id]--;
// }
// rr[id] = rr[id*2+1];
// ll[id] = ll[id*2];
//
// }
//
// long[] qry(int id,int left,int right,int l,int r){
// if(left>=l&&right<=r){
// return new long[]{s[id],ll[id],rr[id]};
// }else if(left>r||right<l){
// return new long[]{0,-1,-1};
// }
// int mid = (left+right)/2;
//
// if(setv[id]!=-1){
// setv[id*2] = setv[id*2+1] = setv[id];
// ll[id*2]=rr[id*2]=ll[id*2+1]=rr[id*2+1] = setv[id];
// s[id*2] = s[id*2+1] = 1;
// setv[id] = -1;
// }
//
//
// long v1[] = qry(id*2,left,mid,l,r);
// long v2[] = qry(id*2+1,mid+1,right,l,r);
// s[id] = s[id*2] + s[id*2+1];
// if(rr[id*2]==ll[id*2+1]){
// s[id]--;
// }
// rr[id] = rr[id*2+1];
// ll[id] = ll[id*2];
// if(v1[0]==0){
// return v2;
// }else if(v2[0]==0){
// return v1;
// }
//
//
// long add = 0;
// if(v1[2]==v2[1]){
// add = -1;
// }
// long le = v1[1];
// long ri = v2[2];
//
// return new long[]{v1[0]+v2[0]+add, le, ri};
// }
// void update(int id,int left,int right,int l,long val){
// if(left>l||right<l){
// return;
// }else if(left==right){
// s[id] += val;
// return;
// }
// int mid = (left+right)/2;
// if(mx[id]!=0){
// mx[id*2] += mx[id];
// mx[id*2+1] += mx[id];
//
// s[id*2] += mx[id]*(mid-left+1);
// s[id*2+1] += mx[id]*(right-(mid+1)+1);
//
//
// mx[id] = 0;
// }
//
// update(id*2,left,mid,l,val);
// update(id*2+1,mid+1,right,l,val);
// s[id] = s[id*2] + s[id*2+1];
//
// }
// void update(int id,int left,int right,int l,int r,long val){
// if(left>r||right<l){
// return;
// }else if(left>=l&&right<=r){
// setv[id] = val;
// ll[id] = val;
// rr[id] = val;
// s[id] = 1;
// return;
// }
// int mid = (left+right)/2;
// if(setv[id]!=-1){
// setv[id*2] = setv[id*2+1] = setv[id];
// ll[id*2]=rr[id*2]=ll[id*2+1]=rr[id*2+1] = setv[id];
// s[id*2] = s[id*2+1] = 1;
// setv[id] = -1;
// }
//
// update(id*2,left,mid,l,r,val);
// update(id*2+1,mid+1,right,l,r,val);
// s[id] = s[id*2] + s[id*2+1];
// if(rr[id*2]==ll[id*2+1]){
// s[id]--;
// }
// rr[id] = rr[id*2+1];
// ll[id] = ll[id*2];
//
// }
int h[],ne[],to[],wt[],c[];
int ct = 0;
void add(int u,int v){
to[ct] = v;
ne[ct] = h[u];
h[u] = ct++;
}
int n;
int time = 0;
int top = 0;
int low[];
boolean iscut[];
int res= 0;
void tarjanNonDirect(int u) {
low[u] = dfn[u]= ++time;
stk[top++] = u;
int child = 0;
for(int i=h[u];i!=-1;i=ne[i]) {
int v = to[i];
if(dfn[v]==0) {
tarjanNonDirect(v);
low[u]=Math.min(low[u],low[v]);
if(low[v]>=dfn[u]){
if(u!=0||++child>1){
iscut[u] = true;
}
}
} else {
low[u] = Math.min(low[u],dfn[v]);
}
}
}
void go() {
while (true) {
time = 0;
top = 0;
res = 0;
ct = 0;
n = in.nextInt();
if (n == 0) {
out.close();
return;
}
// int q = in.nextInt();
h = new int[n];
Arrays.fill(h, -1);
ne = new int[n*n+100];
to = new int[n*n+100];
wt = new int[n];
fa = new int[n];
dep = new int[n];
//top = new int[n];
son = new int[n];
sz = new int[n];
Arrays.fill(sz, 1);
dfn = new int[n];
pt = new int[n];
gpt = new int[n];
stk = new int[n];
c = new int[n];
iscut = new boolean[n];
low = new int[n];
while (true) {
int f = in.nextInt();
if (f == 0) {
break;
}
String y[] = in.nextLine().split(" ");
for (String jj : y) {
if("".equals(jj)) continue;
int p = Integer.parseInt(jj);
add(p - 1, f - 1);
add(f - 1, p - 1);
}
}
tarjanNonDirect(0);
res = 0;
for(int j=0;j<n;++j){
if(iscut[j]){
res++;
}
}
out.println(res);
}
// for(int i= 0;i<n;++i){
// c[i] = in.nextInt();
// wt[i] = in.nextInt();
// }
// for(int i=0;i<n-1;++i){
// int u = in.nextInt()-1;
// int v = in.nextInt()-1;
// add(u,v);
// add(v,u);
// }
// dfs1(0);
// dfs2(0);
// treeLink(0);
// for(int i=0;i<n;++i){
// f[i] = wt[pt[i]];
// }
// s = new int[n*4];
// ll = new int[n*4];
// rr = new int[n*4];
// setv = new int[n*4];
// Arrays.fill(setv,-1);
//
// build(1,0,n-1);
//
// for(int i=0;i<q;++i){
// String c = in.next();
//
// if("C".equals(c)){
// int u = in.nextInt()-1;
// int v = in.nextInt()-1;
// int w = in.nextInt();
// while(top[u]!=top[v]){
// if(dep[top[u]]>=dep[top[v]]){
// update(1,0,n-1,dfn[top[u]],dfn[u],w);
// u = fa[top[u]];
// }else{
// update(1,0,n-1,dfn[top[v]],dfn[v],w);
// v = fa[top[v]];
// }
// }
//
// if(dep[u]>=dep[v]){
// update(1,0,n-1,dfn[v],dfn[u],w);
// }else{
// update(1,0,n-1,dfn[u],dfn[v],w);
// }
// }else{
// int u = in.nextInt()-1;
// int v = in.nextInt()-1;
// long lu = -1000;
// long lv = -1000;
// long r= 0;
// while(top[u]!=top[v]){
// if(dep[top[u]]>=dep[top[v]]){
// long p[] = qry(1,0,n-1,dfn[top[u]],dfn[u]);
// r += p[0];
// if(lu==p[2]){
// r--;
// }
// u = fa[top[u]];
// lu = p[1];
// }else{
// long p[] = qry(1,0,n-1,dfn[top[v]],dfn[v]);
// r += p[0];
// if(lv==p[2]){
// r--;
// }
// v = fa[top[v]];
// lv = p[1];
// }
// }
// if(dep[u]>=dep[v]){
// long p[] = qry(1,0,n-1,dfn[v],dfn[u]);
// r += p[0];
//
// if (p[1] == lv) {
// r--;
// }
// if (p[2] == lu) {
// r--;
// }
//
// }else{
// long p[] = qry(1,0,n-1,dfn[u],dfn[v]);
// r += p[0];
//
// if (p[1] == lu) {
// r--;
// }
// if (p[2] == lv) {
// r--;
// }
//
//
//
// }
// out.println(r);
//
// }
// }
// out.close();
}
int fa[],dep[],son[],sz[],dfn[],pt[],gpt[],stk[];
// void dfs1(int rt){
// sz[rt] = 1;
// for(int i=h[rt];i!=-1;i=ne[i]){
// int v = to[i];
// if(v==fa[rt]) continue;
// fa[v] = rt;
// dep[v] = dep[rt] + 1;
// dfs1(v);
// sz[rt] += sz[v];
// if(son[rt]==0||sz[son[rt]]<sz[v]){
// son[rt] = v;
// }
// }
// }
// int id = 0;
// void dfs2(int rt){
// dfn[rt] = id;
// pt[id++] = rt;
// if(son[rt]!=0){
// top[son[rt]] = top[rt];
// dfs2(son[rt]);
// }
// for(int i=h[rt];i!=-1;i=ne[i]){
// int v = to[i];
// if(v==fa[rt]||v==son[rt]) continue;
// top[v] = v;
// dfs2(v);
// }
// }
//
// public void treeLink(int ort){
// int p = 0;
// stk[p++] = ort;
// int clock = 0;
// int rt = -1;
// while(p>0) {
// rt = stk[--p];
// gpt[clock++] = rt;
// for (int i = h[rt]; i != -1; i = ne[i]) {
// int v = to[i];
// if (fa[rt] == v) continue;
// fa[v] = rt;
// dep[v] = dep[rt] + 1;
// stk[p++] = v;
// }
// }
// for(int i=n-1;i>0;--i){
// int cur = gpt[i];
// int fat = fa[cur];
// sz[fat] += sz[cur];
// if (son[fat]== 0 || sz[cur] > sz[son[fat]]) {
// son[fat] = cur;
// }
// }
// // for (int i = 1; i < n; i++) top[gpt[i]] = gpt[i] == son[fa[gpt[i]]] ? top[fa[gpt[i]]] : gpt[i];
// p = 0;
// stk[p++] = ort;
// while(p>0) {
// rt = stk[--p];
// dfn[rt] = id;
// pt[id++] = rt;
// for (int i = h[rt]; i != -1; i = ne[i]) {
// int v = to[i];
// if (fa[rt] == v || v == son[rt]) continue;
// top[v] = v;
// stk[p++] = v;
// }
// if(son[rt]!=0) {
// top[son[rt]] = top[rt];
// stk[p++] = son[rt];
// }
// }
//
//
// }
}
C++11(clang++ 3.9) 解法, 执行用时: 16ms, 内存消耗: 360K, 提交时间: 2020-05-30 10:21:14
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> G[512];
int dfn[512];
int low[512];
int clk;
int cut_cnt;
void dfs(int s,int f)
{
dfn[s]=low[s]=++clk;
int cnt=0;
bool isCut=false;
for(auto t:G[s])
if(t!=f)
{
if(dfn[t])
low[s]=min(low[s],dfn[t]);
else
{
cnt++;
dfs(t,s);
low[s]=min(low[s],low[t]);
if((f==-1&&cnt>1)||(f!=-1&&dfn[s]<=low[t]))
isCut=true;
}
}
if(isCut) cut_cnt++;
}
void init()
{
for(int i=1;i<=N;i++)
G[i].clear();
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
clk=cut_cnt=0;
}
int main()
{
while(cin>>N&&N)
{
init();
string s;
getline(cin,s);
while(getline(cin,s)&&s!="0")
{
stringstream ss(s);
int u,v;
ss>>u;
while(ss>>v)
G[u].push_back(v),G[v].push_back(u);
}
for(int i=1;i<=N;i++)
if(!dfn[i])
dfs(i,-1);
cout<<cut_cnt<<endl;
}
}