AtCoder Beginner Contest 226 E 图论连通块中DFS判单环思维

57 阅读 0 评论 38 点赞

我是靠谱客的博主害怕黑夜，最近开发中收集的这篇文章主要介绍AtCoder Beginner Contest 226 E 图论连通块中DFS判单环思维，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

给你一个N个点M条无向边的图。
没有自环和重边。
确定每条边的方向，要求让每个点的出度为1。
确定边的方向有几种情况。对998244353取模。

题解思路

当连通块N点M边。
当N==M的时候
就一定有一个自环。（满足连通就需要N-1条边）
当N < M的时候就可能有多个环了。这样某点出度必然为2。
小于时有某个点就出度为0了。

所以，要让每个点出度为1那这个连通块必然就是环了。
这样图里的连通块只能是环并且只有一个单环。
这里在连通块里dfs判环也感觉有点陌生。
在这里插入图片描述

贴大佬的话
大佬的题解

AC代码

#include <bits/stdc++.h>
//#include <unordered_map>
//priority_queue
#define PII pair<int,int>
#define ll long long

using namespace std;

const  int  INF =  0x3f3f3f3f ;
const  int mod = 998244353 ; 
const  int N = 200100 ;
int n , m ;

vector <int> head[200100] ; 
int vis[N] ;
int pp = 0 ; 

void dfs(int p , int fa )
{
    vis[p] = 1 ;
    for (int i = 0 ; i < head[p].size() ; i++ )
    {
        int st = head[p][i] ; 
        if (st == fa )
            continue ; 
        if (!vis[st])
            dfs(st,p) ;
        else
        {
            pp++; 
            //cout << p << " " << st << "n" ; 
            continue ;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m ;
    for (int i = 1 ; i <= m ; i++ )
    {
        int t1 , t2 ;
        cin >> t1 >> t2 ;
        head[t1].push_back(t2) ;
        head[t2].push_back(t1) ; 
    }
    long long ans = 1 ; 
    for (int i = 1 ; i <= n ; i++ )
    {
        if (!vis[i])
        {
            pp = 0 ; 
            dfs(i,-1) ; 
            if ( pp == 2 )
            {
                ans = ans*2 %mod ; 
            }else
            {
                ans = 0 ; 
                break ; 
            }
        }
    }
    cout << ans << "n" ; 
    return 0 ;
}