bzoj1718（邊雙連通分量+貪心）

題面是圖不好截QAQ

就是加點使圖變成一個大的邊雙

先根據已有的邊雙縮點

會形成一棵樹

貪心連葉子結點

答案= （num+1）/2 （ n u m + 1 ） / 2

#include<bits/stdc++.h>
using namespace std;
int n , m , linkk[] ,t;
int dfn[] , low[] , tt;
int color[] , tot , du[];
struct node{
    int n , x , y;
    bool flag;
}e[]; 
int read() {
    bool flag=true;int num=;char c=getchar(); 
    for(;c<'0'||c>'9';c=getchar())if(c=='-') flag=false; 
    for(;c>='0'&&c<='9';c=getchar()) num=(num<<)+(num<<)+c-; 
    if(flag) return num;    else return -num; 
} 
void insert(int x,int y){
    e[++t].x = x;e[t].y = y;e[t].n = linkk[x];linkk[x] = t;
    e[++t].y = x;e[t].x = y;e[t].n = linkk[y];linkk[y] = t;
    return;
}
void trajan(int x,int fa){
    dfn[x] = low[x] = ++tt;
    for(int i = linkk[x];i;i = e[i].n)
       if(!dfn[e[i].y]){
           int y = e[i].y;
           trajan( y , i );
           low[x] = min( low[x] , low[y] ); 
           if(low[y] > dfn[x]){
              e[i].flag = true ,
              e[i ^ ].flag = true;
           }
       }
       else
         if( (i ^ ) != fa)
           low[x] = min( low[x] , dfn[e[i].y] );
    return;
}
void dfs(int x){
    color[x] = tot;
    for(int i = linkk[x];i;i = e[i].n)
       if(!color[e[i].y] && !e[i].flag)
          dfs(e[i].y);
}
void make_node(){
    t = ;
    memset(linkk,,sizeof(linkk));
    for(int i = ;i <= m;++i){
        int j = i * ; 
        int x = e[j].x , y = e[j].y;
        if(color[x] != color[y]) 
          insert( color[x] , color[y] ) ,
          du[color[x]]++,du[color[y]]++;
    }
    return;
}
int get(){
    int sum = ;
    for(int i = ;i <= tot;++i){
        bool flag = true;
        int k = e[linkk[i]].y;
        for(int j = linkk[i];j;j = e[j].n)
          if(e[j].y != k){
             flag = false;
          }
        if(flag) sum++;
    }
    return sum;
}
int main(){
    n = read();m = read();t = ;
    for(int i = ;i <= m;++i){
        int x = read() , y = read();
        insert( x , y );
    }
    trajan(  ,  );
    for(int i = ;i <= n;++i)
      if(!color[i]) ++tot , dfs(i);
    make_node();
    int num = ;
    for(int i = ;i <= tot;++i)
       num += (du[i] == );
    printf("%d",(num+)/);
    return ;
}