本文主要是介绍poj-3352-Road Construction-缩点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
做法：
把所有的边双联通分量缩成一个点。
之后建树，然后求出这个树中度为1的点。
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<stdlib.h> #define INF_MAX 0x7fffffff #define INF 999999 #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; #define ll __int64 #define maxn 10001 #define maxm 100001 struct node {int u;int v;int w;bool friend operator < (node a, node b){return a.w < b.w;} }edge[maxn]; ll gcd(ll n,ll m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);} ll lcm(ll n,ll m){if(n<m) swap(n,m);return n/gcd(n,m)*m;} vector<int>vec[maxn]; vector<int>vect[maxn]; stack<int>st; int n,m,times,nums; int dnf[maxn]; int low[maxn]; int instack[maxn],num[maxn]; int du[maxn],du2[maxn],vis[maxn]; void init() {int i;times=1;nums=1;for(i=0;i<=n;i++){dnf[i]=low[i]=instack[i]=0;num[i]=0;vis[i]=0;vec[i].clear();vect[i].clear();du[i]=du2[i]=0;} } void tarjan(int x,int pre) {int i;low[x]=dnf[x]=times++;instack[x]=1;st.push(x);int len=vec[x].size();for(i=0;i<len;i++){int y=vec[x][i];if(y==pre)continue;if(!dnf[y]){tarjan(y,x);low[x]=min(low[x],low[y]);}else if(instack[y]){low[x]=min(low[x],dnf[y]);}}if(low[x]==dnf[x]){int y=-1;while(y!=x){y=st.top();st.pop();vis[y]=nums;num[nums]++;instack[y]=0;}nums++;} } void jt() {int i,j;i=1;for(i=1;i<=n;i++){int len=vec[i].size();for(j=0;j<len;j++){int x=vis[i];int y=vis[vec[i][j]];if(x==y)continue;du[x]++;du[y]++;}} } int main() {int i,a,b;while(~scanf("%d%d",&n,&m)){init();for(i=0;i<m;i++){scanf("%d%d",&a,&b);vec[a].push_back(b);vec[b].push_back(a);}for(i=1;i<=n;i++)if(!dnf[i])tarjan(i,-1);jt();int t=0;for(i=1;i<nums;i++){if(du[i]==2){t++;}}printf("%d\n",(t+1)/2);}return 0; }
这篇关于poj-3352-Road Construction-缩点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
