Ural 1557 Network Attack

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<string>
  5 #include<iostream>
  6 #include<vector>
  7 using namespace std;
  8 const int maxn = 2005;
  9 const int maxm = 200005;
 10 int nume,ct,n,m;
 11 int g[maxn];
 12 int dfn[maxn];
 13 int s[maxn],t[maxn];
 14 int ma[maxn][maxn];
 15 long long ans;
 16 vector<int>a[maxn];
 17 int tot;
 18 struct edge
 19 {
 20     int v,nxt;
 21 };
 22 edge e[maxm];
 23 void init()
 24 {
 25     nume = 1;
 26     memset(g,0,sizeof(g));
 27 }
 28 void addedge(int u,int v)
 29 {
 30     nume++;
 31     e[nume].v = v;
 32     e[nume].nxt = g[u];
 33     g[u] = nume;
 34 }
 35 void dfs(int x,int edg)
 36 {
 37     ct++;
 38     dfn[x] = ct;
 39     int sum1 =0,sum2 = 0;
 40     for (int i = g[x];i; i = e[i].nxt)
 41     {
 42         if (i == edg || edg == (i ^ 1)) continue;
 43         int y = e[i].v;
 44         if (!dfn[y])
 45         {
 46             a[x].push_back(y);
 47             sum1++;
 48             dfs(y,i);
 49             s[x] = s[x] + s[y];
 50             //cout<<x<<" "<<y<<" "<<s[x]<<" "<<s[y]<<endl;
 51             for (int j = 1; j < dfn[x]; j++) ma[x][j] += ma[y][j];
 52         }
 53         else
 54         {
 55             if (dfn[y] < dfn[x])
 56             {
 57                 sum2++;
 58                 ma[x][dfn[y]]++;
 59             }
 60             else sum1++;
 61         }
 62     }
 63     //cout<<x<<" "<<sum1<<" "<<sum2<<endl;
 64     s[x] = s[x] - sum1 + sum2;
 65 }
 66 void check(int x,int y)
 67 {
 68     for (int i = 0; i < a[x].size(); i++)
 69     {
 70         if (s[y] == s[a[x][i]] && t[a[x][i]] < dfn[y]) ans++;
 71         check(a[x][i],y);
 72     }
 73 }
 74 int main()
 75 {
 76     while (scanf("%d%d",&n,&m) != EOF)
 77     {
 78         init();
 79         for (int i = 1; i <= n; i++) a[i].clear();
 80         int x,y;
 81         for (int i = 1; i <= m; i++)
 82         {
 83             scanf("%d%d",&x,&y);
 84             if (x == y) continue;
 85             addedge(x,y);
 86             addedge(y,x);
 87         }
 88         memset(dfn,0,sizeof(dfn));
 89         memset(s,0,sizeof(s));
 90         memset(t,0,sizeof(t));
 91         memset(ma,0,sizeof(ma));
 92         ct = 0;
 93         for (int i = 2;i <= n; i++) s[i] = 1;
 94         dfs(1,-1);
 95          //for (int i = 1; i <= n; i++) cout<<i<<" "<<s[i]<<endl;
 96         for (int i = 2; i <= n; i++)
 97             for (int j = dfn[i] - 1; j >= 1; j--)
 98               if (ma[i][j] > 0)
 99         {
100             t[i] = j;
101             break;
102         }
103         ans = 0;
104         tot = 0;
105         for (int i = 2; i <= n; i++)
106         {
107             if (s[i] == 1) tot++;
108             else
109             {
110                 if (s[i] == 2) ans++;
111                 check(i,i);
112             }
113         }
114         long long tmp = tot;
115         tmp = tmp * (m - tmp) + tmp * (tmp - 1) / 2;
116         ans = ans + tmp;
117         printf("%I64d\n",ans);
118     }
119     return 0;
120 }