Java 解法, 执行用时: 192ms, 内存消耗: 19152K, 提交时间: 2021-10-02 09:52:27
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
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[];
long res= 0;
int gt = 0;
int fd = 1000000;
int mb = 0;
List<Integer> dcc[];
int dcc_cnt = 0;
void tarjanNonDirect(int u,int fa) {
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(i==(fa^1)) continue;
if(dfn[v]==0) {
tarjanNonDirect(v,i);
low[u]=Math.min(low[u],low[v]);
if(low[v]>dfn[u]){
b[i] = b[i^1] = true;
}
} else {
low[u] = Math.min(low[u],dfn[v]);
}
}
}
void dfs(int rt,int num){
cnt[rt] = num;
for(int i=h[rt];i!=-1;i=ne[i]) {
if(cnt[to[i]]>0||b[i]) continue;
dfs(to[i],num);
}
}
int cnt[];
int d = 0;
int d1 =0;
int all[];
boolean b[];
void go() {
while (true) {
time = 0;
top = 0;
res = 0;
ct = 0;
gt =0;
n = in.nextInt();
d= in.nextInt();
// int q = in.nextInt();
h = new int[n];
Arrays.fill(h, -1);
ne = new int[d*2];
to = new int[d*2];
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];
cnt = new int[n];
b = new boolean[n*n];
while(d-->0){
int p1 = in.nextInt()-1;
int p2 = in.nextInt()-1;
add(p1,p2);
add(p2,p1);
}
tarjanNonDirect(0,-1);
int num = 0;
for(int i=0;i<n;++i){
if(cnt[i]==0){
num++;
dfs(i,num);
}
}
int fk[] = new int[n+1];
for(int i=0;i<ct;++i){
if(b[i]){
fk[cnt[to[i]]]++;
}
}
for(int i=0;i<n+1;++i){
if(fk[i]==1){
res++;
}
}
out.println((res+1)/2);
out.flush();
return;
}
// 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++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 608K, 提交时间: 2019-10-06 18:18:26
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<algorithm>
#define maxn 5010
#define INF 10000
using namespace std;
int low[maxn], dfn[maxn], clor[maxn], df, clr;
vector<int>G[maxn];
void insert(int be, int en) {
G[be].push_back(en);
}
int n, m;
stack<int>s;
int de[maxn];
void tarjan(int x,int fa) {
low[x] = dfn[x] = ++df;
s.push(x);
for (int i = 0; i < G[x].size(); i++) {
int p = G[x][i];
if (p == fa) continue;
if (!dfn[p]) {
tarjan(p, x);
low[x] = min(low[x], low[p]);
}
else {
low[x] = min(low[x], dfn[p]);
}
}
if (low[x] == dfn[x]) {
clr++;
while (1) {
int a = s.top();
s.pop();
clor[a] = clr;
if (a == x) break;
}
}
}
map<long long, int>ins;
int main() {
int be, en;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d %d", &be, &en);
long long an = be * INF + en;
long long cc = en * INF + be;
if (ins[an] == 0 || ins[cc] == 0) {
insert(be, en);
insert(en, be);
ins[cc] = 1;
ins[an] = 1;
}
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i, -1);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < G[i].size(); j++) {
int p = G[i][j];
if (clor[i] != clor[p]) {
de[clor[i]]++;
de[clor[p]]++;
}
}
}
int cnt = 0;
for (int i = 1; i <= clr; i++) {
if (de[i] == 2) cnt++;
}
printf("%d\n", (cnt + 1) / 2);
return 0;
}
C++ 解法, 执行用时: 4ms, 内存消耗: 1188K, 提交时间: 2022-05-30 14:07:16
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
int n,m,cnt=1;
int h[N],ver[N],nt[N],colour,top;
int dfn[N],low[N],dfstime,vis[N],du[N],col[N];
stack<int> st;
void add(int a,int b){
ver[++cnt] = b;
nt[cnt] = h[a];
h[a] = cnt;
}
void tarjan(int x){
dfn[x] = low[x] = ++dfstime;
st.push(x);
for(int i=h[x];~i;i=nt[i])
{
int y=ver[i];
if(!vis[i^1])
{
vis[i]=1;
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else
low[x]=min(low[x],dfn[y]);
}
else
vis[i]=1;
}
int i;
if(low[x]==dfn[x])
{
colour++;
do
{
i=st.top();
st.pop();
col[i]=colour;
}while(i!=x);
}
}
void solve(){
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int x=1;x<=n;x++)
{
for(int i=h[x];~i;i=nt[i])
{
if(vis[i^1])
{
vis[i]=0;
int y=ver[i];
if(col[y]!=col[x])
{
du[col[x]]++;
du[col[y]]++;
}
}
else vis[i]=0;
}
}
int ans=0;
for(int i=1;i<=colour;i++)
if(du[i]==1) ans++;
printf("%d\n",(ans+1)/2);
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
solve();
return 0;
}
