連通圖+最小樹形圖+2-sat

報(bào)名方式：1，將該表交到電教樓522室，時(shí)間下周一，二，三。2，將個(gè)人簡(jiǎn)歷發(fā)送到24758155@。連通圖+最小樹形圖+2-sathdu3594強(qiáng)連通好題仙人掌圖，對(duì)自己的tarjan模板改下用這個(gè)題意：判斷給定的有向圖是否滿足1.強(qiáng)連通2每一條邊屬于且僅屬于一個(gè)環(huán)tarjan算法的運(yùn)用，用fa[]數(shù)組記錄tarjand的搜索路徑，當(dāng)有一個(gè)點(diǎn)有橫向邊（指向它的祖先節(jié)點(diǎn)——表示有環(huán)），據(jù)fa記錄的路徑標(biāo)記除被指向的祖先外所有路徑上的點(diǎn)，當(dāng)有某個(gè)點(diǎn)被記錄2次時(shí)，必然存在一條邊屬于兩個(gè)環(huán)。#include<stdio.h>#include<string.h>#defineN21000structnode{intv,next;}bian[51000];intyong,dfn[N],low[N],stac[N],top,index,visit[N],ans,flag,mark[N],head[N],pre[N];voidinit(){//初始化memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(mark,0,sizeof(mark));memset(visit,0,sizeof(visit));memset(head,-1,sizeof(head));memset(pre,0,sizeof(pre));flag=0;yong=0;index=0;top=0;ans=0;memset(stac,0,sizeof(stac));}voidaddedge(intu,intv){bian[yong].v=v;bian[yong].next=head[u];head[u]=yong++;}intMIN(inta,intb){returna>b?b:a;}voidjudge(intv,intu){//對(duì)于每一個(gè)強(qiáng)連通分量對(duì)邊的兩邊的點(diǎn)增一while(pre[u]!=v){mark[u]++;if(mark[u]>1){flag=1;return;}u=pre[u];}return;}voidtarjan(intu){dfn[u]=low[u]=++index;stac[++top]=u;visit[u]=1;inti;for(i=head[u];i!=-1;i=bian[i].next){intv=bian[i].v;if(dfn[v]==0){pre[v]=u;tarjan(v);if(flag)return;low[u]=MIN(low[u],low[v]);}elseif(visit[v]){judge(v,u);if(flag)return;low[u]=MIN(low[u],dfn[v]);}}if(dfn[u]==low[u]){ans++;if(ans>1){//判斷是否是一個(gè)強(qiáng)聯(lián)通圖flag=1;return;}intt;do{t=stac[top--];visit[t]=0;}while(t!=u);}return;}intmain(){intt,n,a,b,i;scanf("%d",&t);while(t--){init();scanf("%d",&n);while(scanf("%d%d",&a,&b),a||b){addedge(a,b);}for(i=0;i<n;i++){if(!dfn[i])tarjan(i);if(flag)break;}if(flag==0)printf("YES\n");elseprintf("NO\n");}return0;}hdu4009最小樹形圖模板題朱劉算法#include<stdio.h>/*思路：顯然對(duì)于每個(gè)地方，只有一種供水方式就足夠了，這樣也能保證花費(fèi)最小，而每個(gè)地方都可以自己挖井，所以是不可能出現(xiàn)無解的情況的，為了方便思考，我們引入一個(gè)虛擬點(diǎn)，把所有自己挖井的都連到這個(gè)點(diǎn)，邊權(quán)為挖井的花費(fèi)，而如果i能從j處引水，則從j向i連邊，邊權(quán)為引水的花費(fèi)，然后對(duì)這個(gè)有向圖，以虛擬點(diǎn)為根，求最小樹形圖即可（最小樹形圖即為有向圖的最小生成樹）。*/#include<string.h>#include<math.h>#include<stdlib.h>#defineN1100#defineinf999999999structnode{intx,y,z;}f[N];intn;structnodee{intu,v,w;}edge[N*N];intmanhadun(intx,inty){returnabs(f[x].x-f[y].x)+abs(f[x].y-f[y].y)+abs(f[x].z-f[y].z);}intyong,visit[N],pre[N],fffma[N],id[N];voidaddedge(intu,intv,intw){edge[yong].u=u;edge[yong].v=v;edge[yong++].w=w;}intzhuliu(introot){intsum=0,i;while(1){for(i=0;i<=n;i++)fffma[i]=inf;memset(visit,-1,sizeof(visit));memset(id,-1,sizeof(id));for(i=0;i<yong;i++){intu=edge[i].u,v=edge[i].v;if(edge[i].w<fffma[v]&&u!=v){//求所有除根節(jié)點(diǎn)外的點(diǎn)，選擇一天最小權(quán)值的邊pre[v]=u;//記錄前驅(qū)fffma[v]=edge[i].w;}}fffma[root]=0;pre[root]=root;for(i=0;i<=n;i++){//若有孤立點(diǎn)則無解if(fffma[i]==inf)return-1;sum+=fffma[i];}intres=0;for(i=0;i<=n;i++)//所選擇的邊有沒有環(huán)和環(huán)的個(gè)數(shù)if(visit[i]==-1){intv=i;while(visit[v]!=i&&id[v]==-1){//這個(gè)地方需要注意visit[v]=i;v=pre[v];}if(visit[v]!=i||v==root)continue;intu;for(u=pre[v];u!=v;u=pre[u])id[u]=res;id[v]=res++;}if(res==0)returnsum;//如果無環(huán)，則直接返回解for(i=0;i<=n;i++)//將環(huán)外的點(diǎn)都加入if(id[i]==-1)id[i]=res++;for(i=0;i<yong;i++){//縮點(diǎn)出邊不變，入邊變edge[i].w-=fffma[edge[i].v];edge[i].u=id[edge[i].u];edge[i].v=id[edge[i].v];}n=res-1;root=id[root];//相當(dāng)于建立了一個(gè)新圖，root也會(huì)改變}returnsum;}intmain(){inti,j,k,x,y,z;while(scanf("%d%d%d%d",&n,&x,&y,&z),n||x||y||z){yong=0;for(i=1;i<=n;i++){scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z);addedge(0,i,f[i].z*x);//構(gòu)造的虛擬點(diǎn)0為根節(jié)點(diǎn)，權(quán)值為每家建井的費(fèi)用}for(i=1;i<=n;i++){scanf("%d",&k);while(k--){scanf("%d",&j);if(j==i)continue;if(f[j].z>f[i].z)addedge(i,j,manhadun(i,j)*y+z);elseaddedge(i,j,manhadun(i,j)*y);}}printf("%d\n",zhuliu(0));}return0;}hdu3072強(qiáng)連通+縮點(diǎn)+最小樹形圖思想題意：給你n個(gè)點(diǎn)，m條邊，每條邊有一個(gè)權(quán)值（傳送message代價(jià)），已知強(qiáng)連通分支內(nèi)部不需花費(fèi)，求minimalcost#include<stdio.h>#include<string.h>#defineN51000#defineinf1000000000structnode{intu,v,w,next;}bian[N*2];intdfn[N],low[N],yong,index,ans[N],visit[N],head[N],stac[N],top,num,n;voidinit(){yong=0;index=0;top=0;num=0;memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(visit,0,sizeof(visit));memset(stac,0,sizeof(stac));memset(ans,0,sizeof(ans));}voidaddedge(intu,intv,intw){bian[yong].u=u;bian[yong].v=v;bian[yong].w=w;bian[yong].next=head[u];head[u]=yong++;}intmin(inta,intb){returna>b?b:a;}voidtarjan(intu){//求縮點(diǎn)inti;dfn[u]=low[u]=++index;stac[++top]=u;visit[u]=1;for(i=head[u];i!=-1;i=bian[i].next){intv=bian[i].v;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}elseif(visit[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){++num;intt;do{t=stac[top--];visit[t]=0;ans[t]=num;}while(t!=u);}}intmain(){intm,i,j,k,count,dis[N];while(scanf("%d%d",&n,&m)!=EOF){init();while(m--){scanf("%d%d%d",&i,&j,&k);addedge(i,j,k);}for(i=0;i<n;i++)if(!dfn[i])tarjan(i);for(i=1;i<=num;i++)dis[i]=inf;for(i=0;i<yong;i++)if(ans[bian[i].u]!=ans[bian[i].v]){//找到除源點(diǎn)外的進(jìn)入每個(gè)點(diǎn)的最小權(quán)值，所有最小權(quán)值的和就是要求的intv=ans[bian[i].v];if(dis[v]>bian[i].w)dis[v]=bian[i].w;}count=0;for(i=1;i<=num;i++){if(dis[i]<inf)count+=dis[i];}printf("%d\n",count);}return0;hdu2121無根最小樹形圖要建一個(gè)虛擬節(jié)點(diǎn)#include<stdio.h>#include<string.h>#defineinf999999999#defineN1100structnode{intu,v,w;}edge[11000];intvisit[N],dis[N],id[N],pre[N],yong,n,index;voidaddedge(intu,intv,intw){edge[yong].u=u;edge[yong].v=v;edge[yong++].w=w;}intzhuliu(introot){//朱劉算法模板intsum=0;n++;while(1){inti;for(i=0;i<n;i++)dis[i]=inf;memset(id,-1,sizeof(id));memset(visit,-1,sizeof(visit));for(i=0;i<yong;i++){intu=edge[i].u,v=edge[i].v;if(dis[v]>edge[i].w&&u!=v){pre[v]=u;dis[v]=edge[i].w;if(u==root)//記錄最后與根節(jié)點(diǎn)連接的邊index=i;}}pre[root]=root;dis[root]=0;for(i=0;i<n;i++){if(i==root)continue;if(dis[i]==inf)return-1;sum+=dis[i];}intres=0;for(i=0;i<n;i++)if(visit[i]==-1){intv=i;while(visit[v]==-1){visit[v]=i;v=pre[v];}if(visit[v]!=i||v==root)continue;intu;for(u=pre[v];u!=v;u=pre[u])id[u]=res;id[v]=res++;}if(res==0)returnsum;for(i=0;i<n;i++){if(id[i]==-1)id[i]=res++;}for(i=0;i<yong;i++){edge[i].w-=dis[edge[i].v];edge[i].u=id[edge[i].u];edge[i].v=id[edge[i].v];}n=res;root=id[root];}returnsum;}intmain(){intm,i,j,k,maxx,mm;while(scanf("%d%d",&n,&m)!=EOF){yong=0;maxx=0;mm=m;//記錄mwhile(m--){scanf("%d%d%d",&i,&j,&k);maxx+=k;//記錄最大值addedge(i,j,k);}maxx++;//增1for(i=0;i<n;i++)//會(huì)記錄第幾次加入的邊addedge(n,i,maxx);//建立一個(gè)虛擬節(jié)點(diǎn)k=zhuliu(n);if(k==-1||k-maxx>=maxx)printf("impossible\n");elseprintf("%d%d\n",k-maxx,index-mm);//實(shí)際上的根節(jié)點(diǎn)是減去mprintf("\n");}return0;}無向圖求點(diǎn)割集的算法黑書上給出了關(guān)于求點(diǎn)割集的算法，但是比較模糊，我查閱了網(wǎng)絡(luò)上的相關(guān)資料，理解了求點(diǎn)割集的過程，寫出如下求點(diǎn)割集的代碼,并寫了一些簡(jiǎn)單的證明.割點(diǎn)集的定義：如果在連通圖G中去掉某一點(diǎn)后圖不連通，那么這個(gè)點(diǎn)即為G的割點(diǎn)，所有割點(diǎn)的集合即為點(diǎn)割集。求點(diǎn)割集的方法：利用tarjan算法的思想，用數(shù)組dfn[v]存儲(chǔ)DFS遍歷到點(diǎn)v的時(shí)間,數(shù)組low[v]存儲(chǔ)點(diǎn)v能追溯到最早的祖先節(jié)點(diǎn)。如果對(duì)于點(diǎn)v來說有如下結(jié)論：1.如果點(diǎn)v是DFS序列的根節(jié)點(diǎn)，則如果v有一個(gè)以上的孩子，則v是一個(gè)割點(diǎn)。2.如果v不是DFS序列根節(jié)點(diǎn)，并且點(diǎn)v的任意后繼u能追溯到最早的祖先節(jié)點(diǎn)low[u]>=dfn[v]，則v是一個(gè)割點(diǎn)。證明1:假設(shè)DFS遍歷的第一個(gè)節(jié)點(diǎn)v不是割點(diǎn)，那么則有l(wèi)ow[v]=dfn[v]=1，繼續(xù)對(duì)v的孩子節(jié)點(diǎn)u遍歷，必然有l(wèi)ow[u]>=dfn[v]，按照第二條性質(zhì)，則v是割點(diǎn)，但我們已經(jīng)假設(shè)v不是割點(diǎn)。這是由于v是DFS遍歷的起始節(jié)點(diǎn)，在遍歷序列中v沒有祖先節(jié)點(diǎn)，v的所有后繼節(jié)點(diǎn)能追溯到最早的祖先節(jié)點(diǎn)最多也就是v了，不可能比v再早了，因此必須把DFS遍歷的第一個(gè)節(jié)點(diǎn)v單獨(dú)考慮，那么怎么判斷v是不是割點(diǎn)呢？例如上圖，設(shè)v是DFS序列訪問的第一個(gè)節(jié)點(diǎn)，對(duì)v的孩子節(jié)點(diǎn)u和u的所有孩子節(jié)點(diǎn)進(jìn)行DFS遍歷并標(biāo)記為已經(jīng)訪問后，如果v的另一個(gè)孩子節(jié)點(diǎn)k沒有被標(biāo)記為已經(jīng)訪問，那么u和k之間一定不存在邊，也就是說u和k之間的連通必然需要點(diǎn)v，因此如果v是DFS遍歷的第一個(gè)節(jié)點(diǎn)，對(duì)v是否為割點(diǎn)的判斷方法是：看v是不是有多個(gè)孩子，如果有則v是割點(diǎn)。證明2:如果v不是DFS遍歷的第一個(gè)節(jié)點(diǎn)，那么對(duì)于v的所有后繼節(jié)點(diǎn)來說，如果v不是割點(diǎn)（也就是如果刪掉點(diǎn)v，剩下的圖還是連通圖），那么v的后繼節(jié)點(diǎn)必然能追溯到DFS遍歷序列中v的祖先節(jié)點(diǎn)，也就是v的后繼節(jié)點(diǎn)中存在到達(dá)DFS序列中v的祖先的路徑，因此當(dāng)DFS回溯到v節(jié)點(diǎn)時(shí)對(duì)于v的所有后繼節(jié)點(diǎn)u來說，都有l(wèi)ow[u]<dfn[v]。如果v是一個(gè)割點(diǎn)，對(duì)所有v的后繼節(jié)點(diǎn)u進(jìn)行DFS后，必然有l(wèi)ow[u]>=dfn[v]，這是因?yàn)?，?dāng)遍歷v并將其鎖定后，到達(dá)v的祖先節(jié)點(diǎn)的路徑已經(jīng)被封死，v的后繼節(jié)點(diǎn)必然不可能訪問到v的祖先節(jié)點(diǎn)，因此，必然有l(wèi)ow[u]>=dfn[v]。有了上面的分析，下面寫出求無向圖點(diǎn)割集的代碼：#include<iostream>usingnamespacestd;structL{ intv; L*next;};classHEAD{public: intid; L*next; HEAD(){ id=0; next=NULL;}};HEADhead[1000];intdfn[1000],low[1000],t;boollock[1000],C[1000];voidfind(intfather,intv){intcount=0; /*統(tǒng)計(jì)v的孩子數(shù)*/ dfn[v]=low[v]=++t;/*將訪問時(shí)間賦給dfn[v]和low[v]*/ lock[v]=false;/*標(biāo)記v點(diǎn)已經(jīng)訪問過,不能再被訪問*/ for(L*p=head[v].next;p!=NULL;p=p->next) { if(lock[p->v])/*如果v的直接后繼節(jié)點(diǎn)沒有訪問過，則對(duì)其遍歷*/ { find(v,p->v);/*對(duì)v的直接后繼遍歷*/ count++;/*孩子數(shù)+1*/ if(low[v]>low[p->v])/*如果v的孩子能追溯到更早的祖先,則v也能追溯到*/ low[v]=low[p->v]; } elseif(p->v!=father&&low[p->v]<low[v])/*如果v的直接孩子節(jié)點(diǎn)已經(jīng)被訪問過*/ low[v]=low[p->v]; if(!father&&count>1) /*如果當(dāng)前節(jié)點(diǎn)是DFS遍歷到的第一個(gè)節(jié)點(diǎn),則判斷其是否有多個(gè)孩子*/ C[v]=true; elseif(father&&dfn[v]<=low[p->v])/*否則判斷其后繼能否追溯到v的祖先*/ C[v]=true; }}intmain(){ intn,i,a,b; cin>>n; while(cin>>a>>b&&a&&b) /*建立鄰接表,輸入無向圖邊每條ab,以00結(jié)束*/ { L*p=newL; p->next=head[b].next; head[b].next=p; p->v=a; p=newL; p->next=head[a].next; head[a].next=p; p->v=b; head[b].id++; head[a].id++; } memset(lock,true,sizeof(lock)); memset(dfn,0,sizeof(int)*1000); memset(C,0,sizeof(C));/*C數(shù)組用來標(biāo)記那些點(diǎn)是割點(diǎn),剛開始全部置為false*/ t=0;/*訪問時(shí)間*/ find(0,1);/*開始對(duì)1號(hào)點(diǎn)DFS,第一個(gè)遍歷的前驅(qū)節(jié)點(diǎn)設(shè)為0*/ for(i=1;i<=n;i++) /*輸入割點(diǎn)*/ if(C[i]) cout<<i<<''; cout<<endl; 關(guān)于有重邊的強(qiáng)連通分量有向圖的的情況比較簡(jiǎn)單只有一種強(qiáng)連通，重邊和連向自己的邊對(duì)于強(qiáng)連通都沒有任何影響無向圖的雙連通要分點(diǎn)雙連通(biconnected)和邊雙連通(edge_biconnected)，連向自己的邊對(duì)于倆種雙連通也沒有任何影響，但是重邊對(duì)點(diǎn)雙連通沒有影響，但是對(duì)于邊雙連通有影響，因?yàn)樵谇筮呺p連通時(shí)，要求對(duì)于任意倆點(diǎn)至少存在兩條“邊不重復(fù)”的路徑，所以這個(gè)時(shí)候表示圖我們不能用vector了，而是用鄰接表，添加邊的時(shí)候我們要一次添加正反倆條邊，而且要相互可以索引查找，類似網(wǎng)絡(luò)流里的反向弧，這樣在我們dfs求割邊時(shí)要以邊的下標(biāo)作為標(biāo)記，在訪問一了一條邊時(shí)，要把這條邊和其反向邊同時(shí)標(biāo)記為訪問，最后對(duì)所有的邊進(jìn)行遍歷，發(fā)現(xiàn)low[e.v]<pre[e.u]時(shí)，同樣要把正反倆條邊標(biāo)記成割邊，最后在不經(jīng)過橋的情況下dfs求出邊雙連通分量即可structEDGE{ intu,v; intnext;};intfirst[MAXN],rear;EDGEedge[MAXE];voidinit(intn){ memset(first,-1,sizeof(first[0])*(n+1)); rear=0;}voidinsert(inttu,inttv,inttw){ edge[rear].u=tu; edge[rear].v=tv; edge[rear].next=first[tu]; first[tu]=rear++; edge[rear].u=tv; edge[rear].v=tu; edge[rear].next=first[tv]; first[tv]=rear++;}structFIND_BRIDGE{ intpre[MAXN],low[MAXN]; boolvis_e[MAXE];//是否訪問了邊 boolis_bridge[MAXE];//是否是橋 intdfs_clock; voiddfs(intcur) { pre[cur]=low[cur]=++dfs_clock; for(inti=first[cur];~i;i=edge[i].next) { inttv=edge[i].v; if(!pre[tv]) { vis_e[i]=vis_e[i^1]=true; dfs(tv); low[cur]=min(low[cur],low[tv]); if(pre[cur]<low[tv])is_bridge[i]=is_bridge[i^1]=true; } else if(pre[tv]<pre[cur]&&!vis_e[i]) { vis_e[i]=vis_e[i^1]=true; low[cur]=min(low[cur],pre[tv]); } } } voidfind_bridge(intn) { dfs_clock=0; memset(pre,0,sizeof(pre[0])*(n+1)); memset(vis_e,0,sizeof(vis_e[0])*rear); memset(is_bridge,0,sizeof(is_bridge[0])*rear); for(inti=1;i<=n;++i) if(!pre[i]) dfs(i); }}fb;//接著在不經(jīng)過橋的情況下dfs求出所有雙強(qiáng)連通分量即可2767ProvingEquivalences至少加幾條邊讓全部圖變成強(qiáng)連通模板題題意是加多少條邊能使圖成為強(qiáng)連通。。。。#include<stdio.h>#include<string.h>#defineN21000structnode{intu,v,next;}bian[N*3];inthead[N],dfn[N],low[N],index,vis[N],stac[N],top,yong,cnt,suo[N],indegree[N],outdegree[N];voidinit(){yong=0;index=0;top=0;cnt=0;memset(vis,0,sizeof(vis));memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(indegree,0,sizeof(indegree));memset(outdegree,0,sizeof(outdegree));}voidaddedge(intu,intv){bian[yong].u=u;bian[yong].v=v;bian[yong].next=head[u];head[u]=yong++;}intMin(inta,intb){returna>b?b:a;}voidtarjan(intu){dfn[u]=low[u]=++index;vis[u]=1;stac[++top]=u;inti;for(i=head[u];i!=-1;i=bian[i].next){intv=bian[i].v;if(!dfn[v]){tarjan(v);low[u]=Min(low[u],low[v]);}elseif(vis[v])low[u]=Min(low[u],dfn[v]);}if(low[u]==dfn[u]){++cnt;intt;do{t=stac[top--];suo[t]=cnt;vis[t]=0;}while(t!=u);}}intmain(){intn,m,i,in,ou,a,b,t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);if(m==0){printf("%d\n",n);continue;}init();while(m--){scanf("%d%d",&a,&b);addedge(a,b);}for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);if(cnt==1){//剁手printf("0\n");continue;}for(i=0;i<yong;i++)if(suo[bian[i].u]!=suo[bian[i].v]){indegree[suo[bian[i].v]]++;outdegree[suo[bian[i].u]]++;}in=0;ou=0;for(i=1;i<=cnt;i++){if(indegree[i]==0)in++;if(outdegree[i]==0)ou++;}printf("%d\n",in>ou?in:ou);}return0;}hdu3352求邊雙聯(lián)通分量模板題(容器)/*這道題是沒有重邊的，求加幾條邊構(gòu)成雙聯(lián)通，求邊聯(lián)通分量，先求出橋然后縮點(diǎn)，成一個(gè)棵樹找葉子節(jié)點(diǎn)的個(gè)數(shù)*/#include<stdio.h>#include<string.h>#defineN1100inttop[N],ma[N][N],dfn[N],low[N],index,f[N][N],n;intMin(inta,intb){returna>b?b:a;}voidtarjan(intu,intpre){//dfn[u]=low[u]=++index;inti;for(i=0;i<top[u];i++){intv=ma[u][i];if(v==pre)continue;if(!dfn[v]){tarjan(v,u);low[u]=Min(low[u],low[v]);//if(low[v]>dfn[u])//標(biāo)記橋f[u][v]=f[v][u]=1;}elselow[u]=Min(low[u],dfn[v]);}}intcnt,c[N];voiddfs(intu,intfa){//縮點(diǎn)inti;c[u]=cnt;//不能放到循環(huán)里面，for(i=0;i<top[u];i++){intv=ma[u][i];if(!f[u][v]&&!c[v]&&v!=fa)//橋不能走，不能回頭路，沒有被縮過dfs(v,u);}return;}intdegree[N];intslove(){inti,j,b;cnt=1;memset(c,0,sizeof(c));for(i=1;i<=n;i++)//縮點(diǎn)if(!c[i]){dfs(i,-1);cnt++;}memset(degree,0,sizeof(degree));for(i=1;i<=n;i++)for(j=0;j<top[i];j++){b=ma[i][j];if(c[i]!=c[b]){//所有邊中degree[c[i]]++;degree[c[b]]++;//記錄度數(shù)}}intleave=0;for(i=1;i<cnt;i++){//度數(shù)為一的葉子節(jié)點(diǎn)，因?yàn)闉殡p向邊if(degree[i]==2)leave++;}return(leave+1)/2;}intmain(){intm,i,a,b,ans;while(scanf("%d%d",&n,&m)!=EOF){memset(top,0,sizeof(top));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(f,0,sizeof(f));index=0;while(m--){scanf("%d%d",&a,&b);ma[a][top[a]++]=b;//容器ma[b][top[b]++]=a;}for(i=1;i<=n;i++)if(!dfn[i])tarjan(i,-1);ans=slove();printf("%d\n",ans);}return0;}POJ3352無向圖邊雙連通分量，縮點(diǎn)，無重邊為什么寫這道題還是因?yàn)樽蛱於嘈５牡诙}，是道圖論，HDU4612。當(dāng)時(shí)拿到題目的時(shí)候就知道是道模版題，但是苦于圖論太弱。模版都太水，居然找不到。雖然比賽的時(shí)候最后水過了，但是那個(gè)模版看的還是一知半解，主要還是對(duì)于無向圖縮點(diǎn)不了解。所以今天特意找了道求無向圖邊雙連通分量，然后縮點(diǎn)的題學(xué)習(xí)一下，這道題的縮點(diǎn)和昨天那道差不多，唯一的區(qū)別就是這是無重邊的，那題是有重邊的。先搞掉這個(gè)，下午把有重邊的縮點(diǎn)搞一下。這里給出一些概念。具體可以到神牛博客看一下。邊連通度：使一個(gè)子圖不連通的需要?jiǎng)h除掉的最小邊數(shù)，就是該圖的邊連通度。橋（割邊）：刪除某條邊時(shí)，該圖不再連通，那么這條邊就是該圖的橋（割邊）。邊雙連通分量：邊連通度大于等于2的子圖稱為邊連通分量。一個(gè)邊連通分量里面的任意兩點(diǎn)，都有2條或者2條以上的路可以互相到達(dá)。這道題的題意，給出N個(gè)點(diǎn)M條邊，都是無向的。然后叫你求，最少增加多少條邊，可以是的整個(gè)圖成為一個(gè)邊雙聯(lián)通分量。思路：求出所有的邊連通分量，設(shè)數(shù)量為cnt，然后將一個(gè)邊連通分量中的點(diǎn)縮成一個(gè)塊，然后重新建圖，這樣我們就得到了一棵節(jié)點(diǎn)數(shù)為cnt,邊數(shù)為cnt-1,的樹。該樹上的所有邊都是橋。然后要使得這個(gè)圖成為一個(gè)邊連通分量，那么只需將所有的葉子節(jié)點(diǎn)連起來即可。所有最后的答案就是(葉子節(jié)點(diǎn)的個(gè)數(shù)+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>#definePIacos(-1.0)#defineMax2505#defineinf1<<28#defineLL(x)(x<<1)#defineRR(x)(x<<1|1)#defineREP(i,s,t)for(inti=(s);i<=(t);++i)#definelllonglong#definemem(a,b)memset(a,b,sizeof(a))#definemp(a,b)make_pair(a,b)#definePIIpair<int,int>usingnamespacestd;inlinevoidRD(int&ret){charc;do{c=getchar();}while(c<'0'||c>'9');ret=c-'0';while((c=getchar())>='0'&&c<='9')ret=ret*10+(c-'0');}intn,m;structkdq{inte,next;}ed[111111],bridge[1111],reed[11111];inthead[1111],num,rehead[11111],renum;intlow[1111],dfn[1111];intst[11111];intfa[1111];boolvis[1111];intdp;//tarjan的層數(shù)inttop;//棧頂intbridgenum;//橋的數(shù)量intcnt;//縮點(diǎn)后聯(lián)通塊的數(shù)量//可以知道，cnt=bridge+1//縮點(diǎn)后，重新建圖，所有節(jié)點(diǎn)都是一個(gè)聯(lián)通塊，所有的邊都是橋。故有上述結(jié)論。voidinit(){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);}voidadd(ints,inte){ed[num].e=e;ed[num].next=head[s];head[s]=num++;}voidreadd(ints,inte){reed[renum].e=e;reed[renum].next=rehead[s];rehead[s]=renum++;}/***模版求無向圖的雙聯(lián)通分量，縮點(diǎn)，求出橋（無重邊）***/voidtarjan(intnow,intfaa){dfn[now]=low[now]=dp++;st[++top]=now;for(inti=head[now];~i;i=ed[i].next){inte=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;//縮點(diǎn)}while(st[top--]!=e);}}elseif(low[now]>dfn[e])low[now]=dfn[e];}}/***重新建圖***/voidrebuild(){for(inti=1;i<=n;i++){for(intj=head[i];~j;j=ed[j].next){readd(fa[i],fa[ed[j].e]);readd(fa[ed[j].e],fa[i]);}}}intans=0;introot=-1;voiddfs(intnow,intfaa){vis[now]=1;intsum=0;for(inti=rehead[now];~i;i=reed[i].next){inte=reed[i].e;if(e==faa)continue;if(vis[e])continue;sum++;dfs(e,now);}if(!sum)ans++;}voidsolve(){ans=0;rebuild();dfs(root,-1);if(cnt==1)puts("0");elseprintf("%d\n",(ans+1)/2);}intmain(){while(cin>>n>>m){init();while(m--){inta,b;RD(a);RD(b);add(a,b);add(b,a);}for(inti=1;i<=n;i++){//可以處理不連通的圖，如果連通的話，這個(gè)循環(huán)只進(jìn)行一次。if(dfn[i]==0){top=dp=1;tarjan(i,-1);++cnt;for(intj=1;j<=n;j++){//特殊處理頂點(diǎn)的連通塊if(dfn[j]&&fa[j]==-1)fa[j]=cnt,root=cnt;}}}solve();}return0;}網(wǎng)上有一種錯(cuò)誤的做法是:因?yàn)槊恳粋€(gè)雙連通分量?jī)?nèi)的點(diǎn)low[]值都是相同的，則dfs()時(shí)，對(duì)于一條邊(u,v),只需low[u]=min(low[u],low[v])，這樣就不用縮點(diǎn)，最后求度數(shù)的時(shí)候poj3177&&poj3352加邊構(gòu)雙聯(lián)通（有重邊）用tarjan模板求的#include<stdio.h>/*求邊雙聯(lián)通分量和求強(qiáng)連通差不多，先縮點(diǎn)求出葉子節(jié)點(diǎn)的個(gè)數(shù)*/#include<string.h>#defineN5100structnode{intu,v,next;}bian[N*4];intdfn[N],low[N],head[N],index,cnt,yong,stac[N],suo[N],vis[N],top,degree[N];voidinit(){memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));index=0;cnt=0;yong=0;top=0;memset(degree,0,sizeof(degree));}intMin(inta,intb){returna>b?b:a;}voidaddedge(intu,intv){bian[yong].u=u;bian[yong].v=v;bian[yong].next=head[u];head[u]=yong++;}voidtarjan(intu,intfa){dfn[u]=low[u]=++index;vis[u]=1;stac[++top]=u;inti;for(i=head[u];i!=-1;i=bian[i].next){intv=bian[i].v;if(i==(fa^1))continue;//注意優(yōu)先級(jí)if(!dfn[v]){tarjan(v,i);low[u]=Min(low[u],low[v]);}elseif(vis[v])low[u]=Min(low[u],dfn[v]);}if(low[u]==dfn[u]){cnt++;intt;do{t=stac[top--];vis[t]=0;suo[t]=cnt;}while(u!=t);}}intmain(){intn,m,i,a,b;while(scanf("%d%d",&n,&m)!=EOF){init();while(m--){scanf("%d%d",&a,&b);addedge(a,b);addedge(b,a);}for(i=1;i<=n;i++)if(!dfn[i])tarjan(i,-1);for(i=0;i<yong;i++){intu,v;u=bian[i].u;v=bian[i].v;if(suo[u]!=suo[v]){degree[suo[u]]++;degree[suo[v]]++;}}intleave=0;for(i=1;i<=cnt;i++)if(degree[i]==2)leave++;printf("%d\n",(leave+1)/2);}return0;}poj3177&&3352求邊雙聯(lián)通分量，先求橋，然后求分量（臨界表代碼）/*這道題是沒有重邊的，求加幾條邊構(gòu)成雙聯(lián)通，求邊聯(lián)通分量，先求出橋然后縮點(diǎn)，成一個(gè)棵樹找葉子節(jié)點(diǎn)的個(gè)數(shù)*/#include<stdio.h>//用容器寫在3177這個(gè)題上會(huì)超內(nèi)存，但是用臨界表過了#include<string.h>/*此代碼為臨界表代碼*/#defineN5100structnode{intu,v,next;}bian[N*4];intdfn[N],low[N],index,f[N*4],n,head[N],yong;intMin(inta,intb){returna>b?b:a;}voidaddedge(intu,intv){//建邊bian[yong].u=u;bian[yong].v=v;bian[yong].next=head[u];head[u]=yong++;}voidtarjan(intu,intpre){//dfn[u]=low[u]=++index;inti;for(i=head[u];i!=-1;i=bian[i].next){intv=bian[i].v;if(i==(pre^1))continue;if(!dfn[v]){tarjan(v,i);low[u]=Min(low[u],low[v]);//if(low[v]>dfn[u])//標(biāo)記橋f[i]=f[i^1]=1;//標(biāo)記雙向的邊}elselow[u]=Min(low[u],dfn[v]);}}intcnt,c[N];voiddfs(intu,intfa){//縮點(diǎn)inti;c[u]=cnt;//不能放到循環(huán)里面，for(i=head[u];i!=-1;i=bian[i].next){intv=bian[i].v;if(!f[i]&&!c[v]&&i!=(fa^1))//橋不能走，不能回頭路，沒有被縮過dfs(v,i);}return;}intdegree[N];intslove(){inti;cnt=1;memset(c,0,sizeof(c));for(i=1;i<=n;i++)//縮點(diǎn)if(!c[i]){dfs(i,-1);cnt++;}memset(degree,0,sizeof(degree));for(i=0;i<yong;i++){intu,v;u=bian[i].u;v=bian[i].v;if(c[u]!=c[v]){//所有邊中degree[c[u]]++;degree[c[v]]++;//記錄度數(shù)}}intleave=0;for(i=1;i<cnt;i++){//度數(shù)為一的葉子節(jié)點(diǎn)，因?yàn)闉殡p向邊if(degree[i]==2)leave++;}return(leave+1)/2;}intmain(){intm,i,a,b,ans;while(scanf("%d%d",&n,&m)!=EOF){memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(f,0,sizeof(f));yong=0;memset(head,-1,sizeof(head));index=0;while(m--){scanf("%d%d",&a,&b);addedge(a,b);addedge(b,a);}for(i=1;i<=n;i++)if(!dfn[i])tarjan(i,-1);ans=slove();printf("%d\n",ans);}return0;}uva交叉染色法10004鑒于網(wǎng)上講交叉染色的資料比較少，于是我把我自己的心得與方法貼出來，方便與大家共同進(jìn)步。二分圖：百度百科傳送門wiki百科傳送門判斷一個(gè)圖是否為二分圖可以用交叉染色的方法來判斷，可以用BFS，也可以用DFS，這里我用使用DFS來實(shí)現(xiàn)。思路：任意取一個(gè)點(diǎn)進(jìn)行染色，如果發(fā)現(xiàn)要涂某一塊時(shí)這個(gè)塊已經(jīng)被涂了色，并且與我們要使用的顏色不同的話，就說明這個(gè)圖不能被染成BICOLORABLE的。（1）如果沒有染色，將它染色，并將它周圍的點(diǎn)變成相反色。（2）如果已經(jīng)染色，判斷是否與現(xiàn)在染色的點(diǎn)的顏色相同，相同，則退出，否則繼續(xù)。附上例題：UVA10004BicoloringCODE#include<stdio.h>#include<string.h>#defineN300intcolor[N],vis[N];structnode{intu,v,next;}bian[N*N*2];inthead[N],yong;voidaddedge(intu,intv){bian[yong].u=u;bian[yong].v=v;bian[yong].next=head[u];head[u]=yong++;}intfind(intu){inti;for(i=head[u];i!=-1;i=bian[i].next){intv=bian[i].v;if(!vis[v]){vis[v]=1;color[v]=!color[u];find(v);}elseif(color[v]==color[u])return0;}return1;}intmain(){intn,m,a,b;while(scanf("%d",&n),n){scanf("%d",&m);memset(head,-1,sizeof(head));yong=0;memset(color,0,sizeof(color));memset(vis,0,sizeof(vis));while(m--){scanf("%d%d",&a,&b);addedge(a,b);addedge(b,a);}color[0]=1;vis[0]=1;if(find(0))printf("BICOLORABLE.\n");elseprintf("NOTBICOLORABLE.\n");}return0;}hdu2444交叉染色判斷二分圖+二分最大匹配二分匹配。

判斷一個(gè)圖是不是二分圖，是的話求二分匹配最大匹配數(shù)。

主要是怎么判斷一個(gè)圖是不是二分圖。不妨選取某個(gè)點(diǎn)作為起點(diǎn)并

染為某種顏色、同時(shí)把與它相鄰的元素染為對(duì)立的顏色，進(jìn)行BFS，如果

到那步發(fā)現(xiàn)當(dāng)前點(diǎn)和相鄰點(diǎn)的顏色一樣，那么就出現(xiàn)了矛盾，就不是二

分圖。/*1A31ms*/#include<stdio.h>#include<string.h>#defineN300intn;structnode{intu,v,next;}bian[N*N*2];intcolor[N],vis[N],link[N],visit[N],ma[N][N],f[N],head[N],yong;voidaddedge(intu,intv){bian[yong].u=u;bian[yong].v=v;bian[yong].next=head[u];head[u]=yong++;}voidinit(){//初始化memset(ma,0,sizeof(ma));memset(f,0,sizeof(f));memset(visit,0,sizeof(visit));memset(link,-1,sizeof(link));memset(color,0,sizeof(color));memset(vis,0,sizeof(vis));memset(head,-1,sizeof(head));yong=0;}intff(intu){//二分匹配inti;for(i=1;i<=n;i++)if(visit[i]==0&&ma[u][i]){visit[i]=1;if(link[i]==-1||ff(link[i])){link[i]=u;return1;}}return0;}intfind(intu,intf){//交叉染色判定inti;for(i=head[u];i!=-1;i=bian[i].next){intv=bian[i].v;if(f)ma[u][v]=1;//建立鄰接矩陣elsema[v][u]=1;if(!vis[v]){color[v]=!color[u];vis[v]=1;find(v,f^1);}elseif(color[v]==color[u])return0;}return1;}intmain(){intm,i,a,b,ok;while(scanf("%d%d",&n,&m)!=EOF){init();while(m--){scanf("%d%d",&a,&b);addedge(a,b);addedge(b,a);f[a]=f[b]=1;//存在}ok=0;for(i=1;i<=n;i++)if(!vis[i]&&f[i]){color[i]=1;vis[i]=1;if(find(i,1)==0)ok=1;}if(ok){//是否存在不能交叉染色的printf("No\n");continue;}b=0;for(i=1;i<=n;i++){//二分最大匹配memset(visit,0,sizeof(visit));b+=ff(i);}printf("%d\n",b);}return0;}poj2942求點(diǎn)雙聯(lián)通+二分圖判斷奇偶環(huán)+交叉染色法判斷二分圖/lyy289065406/article/details/6756821/wuyiqi/archive/2011/10/19/2217911.html#include"stdio.h"#include"string.h"#def