luogu P2860

Question

https://www.luogu.com.cn/phttps://www.luogu.com.cn/problem/P2860roblem/P2860

#include<bits/stdc++.h>
using namespace std;
int head[5001], cnt;
int n, r;
int dfn[5001], low[5001], bridge[5001], tim;
int scc[5001], du[5001], color_cnt, leaf;
struct {
    int to;
    int next;
} edge[20001];
void add(int x, int y) {
    cnt++;
    edge[cnt] = {y, head[x]};
    head[x] = cnt;
    return;
}
void tarjan(int x, int Edge) {
    dfn[x] = low[x] = ++tim;
    for (int i = head[x]; i; i = edge[i].next) {
        int y = edge[x].to;
        if (!dfn[y]) {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (dfn[x] < low[y]) bridge[i] = bridge[i^1] = 1;
        } else if (i !=Edge^1) low[x] = min(low[x], dfn[y]);
    }
}
void dfs(int x) {
    scc[x] = color_cnt;
    for (int i = head[x]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (bridge[i] || scc[x]) continue;
        dfs(v);
    }
}
int main() {
    cin >> n >> r;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for (int i = 2; i <= cnt; i += 2) {
        if (!dfn[edge[i].to]) tarjan(edge[i].to, i);
    }
    for (int i = 1; i <= n; i++) {
        if (!scc[i]) {
            color_cnt++;
            dfs(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = head[i]; j; j = edge[j].next) {
            if (scc[i] != scc[edge[j].to]) {
                du[edge[j].to]++;
            }
        }
    }
    for (int i = 1; i <= color_cnt; i++) if (du[i]==1) leaf++;
    cout << (leaf + 1)/2;
    return 0;
}

Answer 1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>

using namespace std;
const int MAXN = 5005;
const int MAXM = 10005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}

int n,m,head[MAXN],cnt,to[MAXM<<1],nxt[MAXM<<1],num,du[MAXN];
int dfn[MAXN],low[MAXN],ans,col[MAXN],col_num,stk[MAXN],top;
bool vis[MAXN];
set<pair<int,int> > S;

inline void add(int bg,int ed){
    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}

void tarjan(int x,int fa){
    dfn[x]=low[x]=++num;vis[x]=1;stk[++top]=x;int u;
    for(register int i=head[x];i;i=nxt[i]){
        u=to[i];if(u==fa) continue;
        if(!dfn[u]) {tarjan(u,x);low[x]=min(low[x],low[u]);}
        else if(vis[x])low[x]=min(low[x],dfn[u]);
    }
    if(low[x]!=dfn[x]) return;
    col[x]=++col_num;vis[x]=0;
    while(stk[top]!=x) {
        col[stk[top]]=col_num;
        vis[stk[top--]]=0;
    }top--;
}

int main(){
    n=rd(),m=rd();int x,y;pair<int,int> p;
    for(int i=1;i<=m;i++){
        x=rd(),y=rd();p=make_pair(x,y);
        if(S.find(p)!=S.end()) continue;
        S.insert(p);S.insert(make_pair(y,x));
        add(x,y),add(y,x);
    }
    tarjan(1,1);
//    for(int i=1;i<=n;i++) cout<<col[i]<<" ";
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=nxt[j]) 
            if(col[i]!=col[to[j]]) du[col[i]]++,du[col[to[j]]]++;
    for(int i=1;i<=col_num;i++) if(du[i]==2) ans++;
    cout<<(ans+1)/2;
    return 0;
}
//View Code