1 条题解

  • 0
    @ 2017-08-26 19:26:12

    -------------------------------------------------AC code-------------------------------------------------

    #include<cstdio>
    
    #ifdef WIN32
    #   define outl "%I64d"
    #else
    #   define outl "%lld"
    #endif
    
    using namespace std;
    
    inline int read(){
        int x = 0;
        bool fl = 1;
        char ch = getchar();
        while(ch < '0' || ch > '9'){
            if(ch == '-')   fl = 0;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9'){
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return fl ? x : -x;
    }
    
    /*------------------------------------------------------------------------------------------------------------//
        若将双边看做两条边后,图存在欧拉路,则成立 
        分三种情况讨论: 
        1、自环都为双边:不考虑自环,剩下的点要构成欧拉路则必须有2个奇点,因为单边连的至少一个点是奇点,易知只有两条 
        单边连在同一个顶点上时才满足欧拉路,所以 ans += sum{C(d[i], 2)}
        2、有且仅有一个自环为单边:取任意一条剩下的非单边非自环作为单边即可满足构成欧拉路,所以 ans += loop*(m-loop)
        3、有两个自环为单边:图一定没有奇点,即可构成欧拉回路,所以 ans += C(loop, 2),loop为自环数 
    //------------------------------------------------------------------------------------------------------------*/
    
    typedef long long LL;
    const int MAXN = 100005;
    int n, m, u, v, d[MAXN], loop, fa[MAXN];
    LL ans;
    bool b[MAXN];
    
    int findfa(int x){
        if(fa[x] != x)  fa[x] = findfa(fa[x]);
        return fa[x];
    }
    inline void unionn(int x, int y){
        fa[findfa(y)] = findfa(x);
    }
    
    inline LL C(int x){//calulate C(x, 2)
        return 1ll*x*(x-1)>>1;
    }
    
    int main(){
        n = read(), m = read();
        for(int i = 1; i <= n; i++) fa[i] = i;
        for(int i = 1; i <= m; i++){
            u = read(), v = read();
            if(u == v)  loop++, b[u] = 1;
            else{
                d[u]++, d[v]++;
                if(findfa(u) != findfa(v))  unionn(u, v);
            }
        }
        int f;
        for(int i = 1; i <= n; i++)
            if(b[i] || d[i]){
                f = i;
                break;
            }
        f = findfa(f);
        for(int i = 1; i <= n; i++)
            if(findfa(i) != f && (b[i] || d[i]))
                return puts("0"), 0;
        for(int i = 1; i <= n; i++) ans += C(d[i]);//no loop is one_way edge
        ans += 1ll*loop*(m-loop);                  //one loop is one_way edge
        ans += 1ll*C(loop);                        //two loops are one_way edge
        printf(outl, ans);
        return 0;
    }
    
  • 1

信息

难度
10
分类
图结构 点击显示
标签
递交数
2
已通过
0
通过率
0%
上传者