為什麼寫這道題還是因為昨天多校的第二題，是道圖論，HDU 4612。
當時拿到題目的時候就知道是道模版題，但是苦於圖論太弱。模版都太水，居然找不到。
雖然比賽的時候最後水過了，但是那個模版看的還是一知半解，主要還是對於無向圖縮點不了解。
所以今天特意找了道求無向圖邊雙連通分量，然後縮點的題學習一下，這道題的縮點和昨天那道差不多，唯一的區別就是這是無重邊的，那題是有重邊的。
先搞掉這個，下午把有重邊的縮點搞一下。
這裡給出一些概念。具體可以到神牛博客看一下。
邊連通度：使一個子圖不連通的需要刪除掉的最小邊數，就是該圖的邊連通度。
橋（割邊） ：刪除某條邊時，該圖不再連通，那麼這條邊就是該圖的橋（割邊）。
邊雙連通分量：邊連通度大於等於2的子圖稱為邊連通分量。
一個邊連通分量裡面的任意兩點，都有2條或者2條以上的路可以互相到達。
這道題的題意，給出N個點M條邊，都是無向的。
然後叫你求，最少增加多少條邊，可以是的整個圖成為一個邊雙聯通分量 。
思路：求出所有的邊連通分量，設數量為cnt，然後將一個邊連通分量中的點縮成一個塊，然後重新建圖，這樣我們就得到了一棵節點數為cnt ,邊數為cnt - 1,的樹。
該樹上的所有邊都是橋。
然後要使得這個圖成為一個邊連通分量，那麼只需將所有的葉子節點連起來即可。
所有最後的答案就是(葉子節點的個數+ 1) / 2。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
inline void RD(int &ret) {
char c;
do {
c = getchar();
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
int n , m ;
struct kdq{
int e , next ;
}ed[111111] ,bridge[1111] ,reed[11111] ;
int head[1111] ,num ,rehead[11111] ,renum ;
int low[1111] ,dfn[1111] ;
int st[11111] ;
int fa[1111] ;
bool vis[1111] ;
int dp ; //tarjan的層數
int top ;//棧頂
int bridgenum ;//橋的數量
int cnt ;//縮點後聯通塊的數量
//可以知道，cnt = bridge + 1
//縮點後，重新建圖，所有節點都是一個聯通塊，所有的邊都是橋。故有上述結論。
void init(){
mem(rehead , -1) ;
renum = 0 ;
mem(head , -1) ;
num = 0 ;
dp = 0 ;
top = 0 ;
bridgenum = 0 ;
cnt = 0 ;
mem(low ,0) ;
mem(dfn ,0) ;
mem(fa,-1) ;
mem(vis, 0 ) ;
}
void add(int s ,int e){
ed[num].e = e ;
ed[num].next = head[s] ;
head[s] = num ++ ;
}
void readd(int s ,int e){
reed[renum].e = e ;
reed[renum].next = rehead[s] ;
rehead[s] = renum ++ ;
}
/***模版求無向圖的雙聯通分量，縮點，求出橋（無重邊）***/
void tarjan(int now ,int faa){
dfn[now] = low[now] = dp ++ ;
st[++ top] = now ;
for (int i = head[now] ; ~i ;i = ed[i].next ){
int e = ed[i].e ;
if(e == faa)continue ;
if(dfn[e] == 0){
tarjan(e ,now) ;
if(low[e] < low[now])low[now] = low[e] ;
if(low[e] > dfn[now]){
bridge[bridgenum].e = now ;//橋
bridge[bridgenum ++].next = e ;
cnt ++ ;
do{
fa[st[top]] = cnt ;//縮點
}while(st[top --] != e) ;
}
}else if(low[now] > dfn[e])low[now] = dfn[e] ;
}
}
/***重新建圖***/
void rebuild(){
for (int i = 1 ; i <= n ; i ++ ){
for (int j = head[i] ; ~j ; j = ed[j].next){
readd(fa[i], fa[ed[j].e]) ;
readd(fa[ed[j].e] ,fa[i]) ;
}
}
}
int ans = 0 ;
int root = -1 ;
void dfs(int now ,int faa){
vis[now] = 1 ;
int sum = 0 ;
for(int i = rehead[now] ; ~i ;i = reed[i].next){
int e = reed[i].e ;
if(e == faa)continue ;
if(vis[e])continue ;
sum ++ ;
dfs(e,now) ;
}
if(!sum)ans ++ ;
}
void solve(){
ans = 0 ;
rebuild() ;
dfs(root ,-1) ;
if(cnt == 1)puts("0") ;
else
printf("%d\n",(ans + 1) / 2) ;
}
int main() {
while(cin >> n >> m){
init() ;
while(m -- ){
int a , b ;
RD(a) ;RD(b) ;
add(a , b) ;
add(b , a) ;
}
for (int i = 1 ;i <= n ;i ++ ){//可以處理不連通的圖，如果連通的話，這個循環只進行一次。
if(dfn[i] == 0){
top = dp = 1 ;
tarjan(i , -1) ;
++ cnt ;
for (int j = 1 ; j <= n ;j ++ ){//特殊處理頂點的連通塊
if(dfn[j] && fa[j] == -1)fa[j] = cnt ,root = cnt;
}
}
}
solve() ;
}
return 0 ;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
inline void RD(int &ret) {
char c;
do {
c = getchar();
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
int n , m ;
struct kdq{
int e , next ;
}ed[111111] ,bridge[1111] ,reed[11111] ;
int head[1111] ,num ,rehead[11111] ,renum ;
int low[1111] ,dfn[1111] ;
int st[11111] ;
int fa[1111] ;
bool vis[1111] ;
int dp ; //tarjan的層數
int top ;//棧頂
int bridgenum ;//橋的數量
int cnt ;//縮點後聯通塊的數量
//可以知道，cnt = bridge + 1
//縮點後，重新建圖，所有節點都是一個聯通塊，所有的邊都是橋。故有上述結論。
void init(){
mem(rehead , -1) ;
renum = 0 ;
mem(head , -1) ;
num = 0 ;
dp = 0 ;
top = 0 ;
bridgenum = 0 ;
cnt = 0 ;
mem(low ,0) ;
mem(dfn ,0) ;
mem(fa,-1) ;
mem(vis, 0 ) ;
}
void add(int s ,int e){
ed[num].e = e ;
ed[num].next = head[s] ;
head[s] = num ++ ;
}
void readd(int s ,int e){
reed[renum].e = e ;
reed[renum].next = rehead[s] ;
rehead[s] = renum ++ ;
}
/***模版求無向圖的雙聯通分量，縮點，求出橋（無重邊）***/
void tarjan(int now ,int faa){
dfn[now] = low[now] = dp ++ ;
st[++ top] = now ;
for (int i = head[now] ; ~i ;i = ed[i].next ){
int e = ed[i].e ;
if(e == faa)continue ;
if(dfn[e] == 0){
tarjan(e ,now) ;
if(low[e] < low[now])low[now] = low[e] ;
if(low[e] > dfn[now]){
bridge[bridgenum].e = now ;//橋
bridge[bridgenum ++].next = e ;
cnt ++ ;
do{
fa[st[top]] = cnt ;//縮點
}while(st[top --] != e) ;
}
}else if(low[now] > dfn[e])low[now] = dfn[e] ;
}
}
/***重新建圖***/
void rebuild(){
for (int i = 1 ; i <= n ; i ++ ){
for (int j = head[i] ; ~j ; j = ed[j].next){
readd(fa[i], fa[ed[j].e]) ;
readd(fa[ed[j].e] ,fa[i]) ;
}
}
}
int ans = 0 ;
int root = -1 ;
void dfs(int now ,int faa){
vis[now] = 1 ;
int sum = 0 ;
for(int i = rehead[now] ; ~i ;i = reed[i].next){
int e = reed[i].e ;
if(e == faa)continue ;
if(vis[e])continue ;
sum ++ ;
dfs(e,now) ;
}
if(!sum)ans ++ ;
}
void solve(){
ans = 0 ;
rebuild() ;
dfs(root ,-1) ;
if(cnt == 1)puts("0") ;
else
printf("%d\n",(ans + 1) / 2) ;
}
int main() {
while(cin >> n >> m){
init() ;
while(m -- ){
int a , b ;
RD(a) ;RD(b) ;
add(a , b) ;
add(b , a) ;
}
for (int i = 1 ;i <= n ;i ++ ){//可以處理不連通的圖，如果連通的話，這個循環只進行一次。
if(dfn[i] == 0){
top = dp = 1 ;
tarjan(i , -1) ;
++ cnt ;
for (int j = 1 ; j <= n ;j ++ ){//特殊處理頂點的連通塊
if(dfn[j] && fa[j] == -1)fa[j] = cnt ,root = cnt;
}
}
}
solve() ;
}
return 0 ;
}
