连通图+最小树形图+2-sat

报名方式：1，将该表交到电教楼522室，时间下周一，二，三。2，将个人简历发送到24758155@。连通图+最小树形图+2-sathdu3594强连通好题仙人掌图，对自己的tarjan模板改下用这个题意：判断给定的有向图是否满足1.强连通2每一条边属于且仅属于一个环tarjan算法的运用，用fa[]数组记录tarjand的搜索路径，当有一个点有横向边（指向它的祖先节点——表示有环），据fa记录的路径标记除被指向的祖先外所有路径上的点，当有某个点被记录2次时，必然存在一条边属于两个环。#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){//对于每一个强连通分量对边的两边的点增一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){//判断是否是一个强联通图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>/*思路：显然对于每个地方，只有一种供水方式就足够了，这样也能保证花费最小，而每个地方都可以自己挖井，所以是不可能出现无解的情况的，为了方便思考，我们引入一个虚拟点，把所有自己挖井的都连到这个点，边权为挖井的花费，而如果i能从j处引水，则从j向i连边，边权为引水的花费，然后对这个有向图，以虚拟点为根，求最小树形图即可（最小树形图即为有向图的最小生成树）。*/#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){//求所有除根节点外的点，选择一天最小权值的边pre[v]=u;//记录前驱fffma[v]=edge[i].w;}}fffma[root]=0;pre[root]=root;for(i=0;i<=n;i++){//若有孤立点则无解if(fffma[i]==inf)return-1;sum+=fffma[i];}intres=0;for(i=0;i<=n;i++)//所选择的边有没有环和环的个数if(visit[i]==-1){intv=i;while(visit[v]!=i&&id[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-=fffma[edge[i].v];edge[i].u=id[edge[i].u];edge[i].v=id[edge[i].v];}n=res-1;root=id[root];//相当于建立了一个新图，root也会改变}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);//构造的虚拟点0为根节点，权值为每家建井的费用}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强连通+缩点+最小树形图思想题意：给你n个点，m条边，每条边有一个权值（传送message代价），已知强连通分支内部不需花费，求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){//求缩点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]){//找到除源点外的进入每个点的最小权值，所有最小权值的和就是要求的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无根最小树形图要建一个虚拟节点#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)//记录最后与根节点连接的边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++)//会记录第几次加入的边addedge(n,i,maxx);//建立一个虚拟节点k=zhuliu(n);if(k==-1||k-maxx>=maxx)printf("impossible\n");elseprintf("%d%d\n",k-maxx,index-mm);//实际上的根节点是减去mprintf("\n");}return0;}无向图求点割集的算法黑书上给出了关于求点割集的算法，但是比较模糊，我查阅了网络上的相关资料，理解了求点割集的过程，写出如下求点割集的代码,并写了一些简单的证明.割点集的定义：如果在连通图G中去掉某一点后图不连通，那么这个点即为G的割点，所有割点的集合即为点割集。求点割集的方法：利用tarjan算法的思想，用数组dfn[v]存储DFS遍历到点v的时间,数组low[v]存储点v能追溯到最早的祖先节点。如果对于点v来说有如下结论：1.如果点v是DFS序列的根节点，则如果v有一个以上的孩子，则v是一个割点。2.如果v不是DFS序列根节点，并且点v的任意后继u能追溯到最早的祖先节点low[u]>=dfn[v]，则v是一个割点。证明1:假设DFS遍历的第一个节点v不是割点，那么则有low[v]=dfn[v]=1，继续对v的孩子节点u遍历，必然有low[u]>=dfn[v]，按照第二条性质，则v是割点，但我们已经假设v不是割点。这是由于v是DFS遍历的起始节点，在遍历序列中v没有祖先节点，v的所有后继节点能追溯到最早的祖先节点最多也就是v了，不可能比v再早了，因此必须把DFS遍历的第一个节点v单独考虑，那么怎么判断v是不是割点呢？例如上图，设v是DFS序列访问的第一个节点，对v的孩子节点u和u的所有孩子节点进行DFS遍历并标记为已经访问后，如果v的另一个孩子节点k没有被标记为已经访问，那么u和k之间一定不存在边，也就是说u和k之间的连通必然需要点v，因此如果v是DFS遍历的第一个节点，对v是否为割点的判断方法是：看v是不是有多个孩子，如果有则v是割点。证明2:如果v不是DFS遍历的第一个节点，那么对于v的所有后继节点来说，如果v不是割点（也就是如果删掉点v，剩下的图还是连通图），那么v的后继节点必然能追溯到DFS遍历序列中v的祖先节点，也就是v的后继节点中存在到达DFS序列中v的祖先的路径，因此当DFS回溯到v节点时对于v的所有后继节点u来说，都有low[u]<dfn[v]。如果v是一个割点，对所有v的后继节点u进行DFS后，必然有low[u]>=dfn[v]，这是因为，当遍历v并将其锁定后，到达v的祖先节点的路径已经被封死，v的后继节点必然不可能访问到v的祖先节点，因此，必然有low[u]>=dfn[v]。有了上面的分析，下面写出求无向图点割集的代码：#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; /*统计v的孩子数*/ dfn[v]=low[v]=++t;/*将访问时间赋给dfn[v]和low[v]*/ lock[v]=false;/*标记v点已经访问过,不能再被访问*/ for(L*p=head[v].next;p!=NULL;p=p->next) { if(lock[p->v])/*如果v的直接后继节点没有访问过，则对其遍历*/ { find(v,p->v);/*对v的直接后继遍历*/ count++;/*孩子数+1*/ if(low[v]>low[p->v])/*如果v的孩子能追溯到更早的祖先,则v也能追溯到*/ low[v]=low[p->v]; } elseif(p->v!=father&&low[p->v]<low[v])/*如果v的直接孩子节点已经被访问过*/ low[v]=low[p->v]; if(!father&&count>1) /*如果当前节点是DFS遍历到的第一个节点,则判断其是否有多个孩子*/ 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结束*/ { 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数组用来标记那些点是割点,刚开始全部置为false*/ t=0;/*访问时间*/ find(0,1);/*开始对1号点DFS,第一个遍历的前驱节点设为0*/ for(i=1;i<=n;i++) /*输入割点*/ if(C[i]) cout<<i<<''; cout<<endl; 关于有重边的强连通分量有向图的的情况比较简单只有一种强连通，重边和连向自己的边对于强连通都没有任何影响无向图的双连通要分点双连通(biconnected)和边双连通(edge_biconnected)，连向自己的边对于俩种双连通也没有任何影响，但是重边对点双连通没有影响，但是对于边双连通有影响，因为在求边双连通时，要求对于任意俩点至少存在两条“边不重复”的路径，所以这个时候表示图我们不能用vector了，而是用邻接表，添加边的时候我们要一次添加正反俩条边，而且要相互可以索引查找，类似网络流里的反向弧，这样在我们dfs求割边时要以边的下标作为标记，在访问一了一条边时，要把这条边和其反向边同时标记为访问，最后对所有的边进行遍历，发现low[e.v]<pre[e.u]时，同样要把正反俩条边标记成割边，最后在不经过桥的情况下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;//接着在不经过桥的情况下dfs求出所有双强连通分量即可2767ProvingEquivalences至少加几条边让全部图变成强连通模板题题意是加多少条边能使图成为强连通。。。。#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求边双联通分量模板题(容器)/*这道题是没有重边的，求加几条边构成双联通，求边联通分量，先求出桥然后缩点，成一个棵树找叶子节点的个数*/#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])//标记桥f[u][v]=f[v][u]=1;}elselow[u]=Min(low[u],dfn[v]);}}intcnt,c[N];voiddfs(intu,intfa){//缩点inti;c[u]=cnt;//不能放到循环里面，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++)//缩点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]]++;//记录度数}}intleave=0;for(i=1;i<cnt;i++){//度数为一的叶子节点，因为为双向边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无向图边双连通分量，缩点，无重边为什么写这道题还是因为昨天多校的第二题，是道图论，HDU4612。当时拿到题目的时候就知道是道模版题，但是苦于图论太弱。模版都太水，居然找不到。虽然比赛的时候最后水过了，但是那个模版看的还是一知半解，主要还是对于无向图缩点不了解。所以今天特意找了道求无向图边双连通分量，然后缩点的题学习一下，这道题的缩点和昨天那道差不多，唯一的区别就是这是无重边的，那题是有重边的。先搞掉这个，下午把有重边的缩点搞一下。这里给出一些概念。具体可以到神牛博客看一下。边连通度：使一个子图不连通的需要删除掉的最小边数，就是该图的边连通度。桥（割边）：删除某条边时，该图不再连通，那么这条边就是该图的桥（割边）。边双连通分量：边连通度大于等于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>#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的层数inttop;//栈顶intbridgenum;//桥的数量intcnt;//缩点后联通块的数量//可以知道，cnt=bridge+1//缩点后，重新建图，所有节点都是一个联通块，所有的边都是桥。故有上述结论。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++;}/***模版求无向图的双联通分量，缩点，求出桥（无重边）***/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;//缩点}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++){//可以处理不连通的图，如果连通的话，这个循环只进行一次。if(dfn[i]==0){top=dp=1;tarjan(i,-1);++cnt;for(intj=1;j<=n;j++){//特殊处理顶点的连通块if(dfn[j]&&fa[j]==-1)fa[j]=cnt,root=cnt;}}}solve();}return0;}网上有一种错误的做法是:因为每一个双连通分量内的点low[]值都是相同的，则dfs()时，对于一条边(u,v),只需low[u]=min(low[u],low[v])，这样就不用缩点，最后求度数的时候poj3177&&poj3352加边构双联通（有重边）用tarjan模板求的#include<stdio.h>/*求边双联通分量和求强连通差不多，先缩点求出叶子节点的个数*/#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;//注意优先级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求边双联通分量，先求桥，然后求分量（临界表代码）/*这道题是没有重边的，求加几条边构成双联通，求边联通分量，先求出桥然后缩点，成一个棵树找叶子节点的个数*/#include<stdio.h>//用容器写在3177这个题上会超内存，但是用临界表过了#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])//标记桥f[i]=f[i^1]=1;//标记双向的边}elselow[u]=Min(low[u],dfn[v]);}}intcnt,c[N];voiddfs(intu,intfa){//缩点inti;c[u]=cnt;//不能放到循环里面，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++)//缩点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]]++;//记录度数}}intleave=0;for(i=1;i<cnt;i++){//度数为一的叶子节点，因为为双向边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鉴于网上讲交叉染色的资料比较少，于是我把我自己的心得与方法贴出来，方便与大家共同进步。二分图：百度百科传送门wiki百科传送门判断一个图是否为二分图可以用交叉染色的方法来判断，可以用BFS，也可以用DFS，这里我用使用DFS来实现。思路：任意取一个点进行染色，如果发现要涂某一块时这个块已经被涂了色，并且与我们要使用的颜色不同的话，就说明这个图不能被染成BICOLORABLE的。（1）如果没有染色，将它染色，并将它周围的点变成相反色。（2）如果已经染色，判断是否与现在染色的点的颜色相同，相同，则退出，否则继续。附上例题：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交叉染色判断二分图+二分最大匹配二分匹配。

判断一个图是不是二分图，是的话求二分匹配最大匹配数。

主要是怎么判断一个图是不是二分图。不妨选取某个点作为起点并

染为某种颜色、同时把与它相邻的元素染为对立的颜色，进行BFS，如果

到那步发现当前点和相邻点的颜色一样，那么就出现了矛盾，就不是二

分图。/*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求点双联通+二分图判断奇偶环+交叉染色法判断二分图/lyy289065406/article/details/6756821/wuyiqi/archive/2011/10/19/2217911.html#include"stdio.h"#include"string.h"#def