Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:为啥我的程序能过啊?

Posted by Stabber_dove at 2016-09-12 16:59:55 on Problem 3177
In Reply To:为啥我的程序能过啊? Posted by:Jj1729 at 2012-04-19 16:32:15
> 代码比较丑……
> 
> #include <cstdio>
> #include <cstdlib>
> #include <algorithm>
> #include <string>
> 
> const int maxN = 5010;
> struct Edge
> {
>     int v; bool bridge;
>     Edge *next, *back; Edge() {}
>     Edge(int v, Edge *next):
>         v(v), next(next), bridge(0) {}
> } *edge[maxN], *bridge[maxN];
> bool marked[maxN];
> int DFN[maxN], Low[maxN], stack[maxN];
> int Belong[maxN], Degree[maxN];
> int root, Dcnt, Ind, leaf, top, n, m;
> 
> inline int getint()
> {
>     int res = 0; char tmp;
>     while (!isdigit(tmp = getchar()));
>     do res = (res << 3) + (res << 1) + tmp - '0';
>     while (isdigit(tmp = getchar()));
>     return res;
> }
> 
> void tarjan(int u, int Last)
> {
>     DFN[u] = Low[u] = ++Ind;
>     marked[stack[++top] = u] = 1;
>     for (Edge *p = edge[u]; p; p = p -> next)
>     if (p -> v != Last)
> //这样每次判断不等于父亲好像在有重边的情况下要错
>     {
>         int v = p -> v;
>         if (!DFN[v])
>         {
>             tarjan(v, u);
>             Low[u] = std::min(Low[u], Low[v]);
>             if (DFN[u] < Low[v])
>             {
>                 p -> back -> bridge = p -> bridge = 1;
> //标记为桥。
>                 ++Dcnt; int tmp = v;
>                 do
>                 {
>                     tmp = stack[top--];
>                     marked[tmp] = 0;
>                     Belong[tmp] = Dcnt;
>                 } while (tmp - v);
>             }
>         }
>         else if (marked[v])
>             Low[u] = std::min(Low[u], DFN[v]);
>     }
>     return;
> }
> 
> int main()
> {
>     freopen("Redundant_Paths.in", "r", stdin);
>     freopen("Redundant_Paths.out", "w", stdout);
>     n = getint(); m = getint();
>     while (m--)
>     {
>         int u = getint(), v = getint();
>         edge[u] = new Edge(v, edge[u]);
>         edge[v] = new Edge(u, edge[v]);
>         edge[u] -> back = edge[v];
>         edge[v] -> back = edge[u];
>     }
>     tarjan(1, -1); int tmp = 1; ++Dcnt;
>     do
>     {
>         tmp = stack[top--];
>         marked[tmp] = 0;
>         Belong[tmp] = Dcnt;
>     } while (tmp - 1);
> //最后把根所在的双联通分量取出来。
>     for (int u = 1; u < n + 1; ++u)
>     for (Edge *p = edge[u]; p; p = p -> next)
>     if (p -> bridge)
> //这句要是改成if (Belong[u]!=Belong[p->v])就WA了……
>     {
>         int v = p -> v;
>         bridge[Belong[u]] = new
>             Edge(Belong[v], bridge[Belong[u]]);
>     }
>     int leaf = 0;
>     for (int u = 1; u < Dcnt + 1; ++u)
>     {
>         for (Edge *p = bridge[u]; p; p = p -> next)
>             ++Degree[u];
>         if (Degree[u] == 1) ++leaf;
>     }
>     printf("%d\n", leaf == 1 ? 0 : (leaf + 1 >> 1));
>     return 0;
> }
> 
> 比如这组数据:
> 5 23
> 1 2
> 5 4
> 4 1
> 4 3
> 5 3
> 1 5
> 4 1
> 3 1
> 3 1
> 1 3
> 4 5
> 1 2
> 4 5
> 3 5
> 4 5
> 1 4
> 3 5
> 4 5
> 5 1
> 4 5
> 2 1
> 1 4
> 5 4
> 正确答案是0,但我的程序输出1。
我输出的是0,但是是wa了

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator