【POJ3352】Road Construction（边双联通分量）

题意：给一个无向图，问最少添加多少条边后能使整个图变成双连通分量。

思路：双连通分量缩点，缩点后给度为1的分量两两之间连边，要连(ans+1) div 2条

low[u]即为u所在的分量编号，flag=0,1,2表示没搜过，没搜完，搜完了

POJ上pascal编译器出问题了不管怎么交都CE

这次写的应该能处理重边

 var head,vet,next,flag,dfn,low,fan,de:array[..]of longint;

     n,m,i,e,v,ans,x,y,tot,time:longint;

 procedure add(a,b:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  head[a]:=tot;

 end;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 procedure dfs(u,le:longint);

 var e,v:longint;

 begin

  flag[u]:=;

  inc(time); dfn[u]:=time; low[u]:=time;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if e=fan[le] then

   begin

    e:=next[e];

    continue;

   end;

   if flag[v]= then

   begin

    dfs(v,e);

    low[u]:=min(low[u],low[v]);

   end

    else if flag[v]= then low[u]:=min(low[u],dfn[v]);

   e:=next[e];

  end;

  flag[u]:=;

 end;

 begin

  for i:= to  do

    if i mod = then fan[i]:=i+

     else fan[i]:=i-;

  while not eof do

  begin

   readln(n,m);

   if (n=)and(m=) then break;

   fillchar(head,sizeof(head),);

   fillchar(low,sizeof(low),);

   fillchar(de,sizeof(de),);

   fillchar(flag,sizeof(flag),);

   tot:=; time:=;

   for i:= to m do

   begin

    read(x,y);

    add(x,y);

    add(y,x);

   end;

   for i:= to n do

    if flag[i]= then dfs(i,);

   for i:= to n do

   begin

    e:=head[i];

    while e<> do

    begin

     v:=vet[e];

     if low[v]<>low[i] then inc(de[low[i]]);

     e:=next[e];

    end;

   end;

   ans:=;

   for i:= to n do

    if de[i]= then inc(ans);

   writeln((ans+) div );

  end;

 end.

这个是去年写的那时候AC了好像不能处理重边

 var de,low,next,vet,head,flag,dfn:array[..]of longint;

     n,m,tot,x,y,i,e,v,leaf,time:longint;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(X);

  exit(y);

 end;

 procedure add(a,b:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  head[a]:=tot;

 end;

 procedure dfs(u,fa:longint);

 var e,v:longint;

 begin

  inc(time);

  dfn[u]:=time; low[u]:=time;

  flag[u]:=;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v=fa then

   begin

    e:=next[e];

    continue;

   end;

   if flag[v]= then

   begin

    dfs(v,u);

    low[u]:=min(low[u],low[v]);

   end

    else if flag[v]= then low[u]:=min(low[u],dfn[v]);

   e:=next[e];

  end;

  flag[u]:=;

 end;

 begin

  while not eof do

  begin

   readln(n,m);

   if (n=)and(m=) then break;

   fillchar(head,sizeof(head),);

   tot:=;

   for i:= to m do

   begin

    readln(x,y);

    add(x,y);

    add(y,x);

   end;

   fillchar(dfn,sizeof(dfn),);

   fillchar(de,sizeof(de),);

   fillchar(flag,sizeof(flag),);

   time:=;

   for i:= to n do

    if flag[i]= then dfs(i,i);

   for i:= to n do

   begin

    e:=head[i];

    while e<> do

    begin

     v:=vet[e];

     if low[i]<>low[v] then inc(de[low[i]]);

     e:=next[e];

    end;

   end;

   leaf:=;

   for i:= to n do

    if de[i]= then inc(leaf);

   writeln((leaf+) div );

  end;

 end.

UPD（2018.10.18）：C++

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N   15000

 #define M   6100000

 #define eps 1e-8

 #define pi  acos(-1)

 #define oo  1e9

 int head[N],vet[N],nxt[N],flag[N],dfn[N],low[N],fan[N],d[N],

     tot,tim;

 void add(int a,int b)

 {

     nxt[++tot]=head[a];

     vet[tot]=b;

     head[a]=tot;

 }

 void dfs(int u,int le)

 {

     flag[u]=;

     dfn[u]=low[u]=++tim;

     int e=head[u];

     while(e)

     {

         int v=vet[e];

         if(e==fan[le])

         {

             e=nxt[e];

             continue;

         }

         if(!flag[v])

         {

             dfs(v,e);

             low[u]=min(low[u],low[v]);

         }

          else if(flag[v]==) low[u]=min(low[u],dfn[v]);

         e=nxt[e];

     }

     flag[u]=;

 }

 int main()

 {

     freopen("poj3352.in","r",stdin);

     freopen("poj3352.out","w",stdout);

     for(int i=;i<=;i++)

      if(i&) fan[i]=i+;

       else fan[i]=i-;

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         memset(head,,sizeof(head));

         memset(low,,sizeof(low));

         memset(d,,sizeof(d));

         memset(flag,,sizeof(flag));

         tot=tim=;

         for(int i=;i<=m;i++)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             add(x,y);

             add(y,x);

         }

         for(int i=;i<=n;i++)

          if(flag[i]==) dfs(i,);

         for(int i=;i<=n;i++)

         {

             int e=head[i];

             while(e)

             {

                 int v=vet[e];

                 if(low[v]!=low[i]) d[low[i]]++;

                 e=nxt[e];

             }

         }

         int ans=;

         for(int i=;i<=n;i++)

          if(d[i]==) ans++;

         printf("%d\n",(ans+)/);

     }

     return ;

 }

巴特西

【POJ3352】Road Construction（边双联通分量）

最新文章

热门文章