3 solutions

  • 8
    @ 2024-6-7 13:34:14

    题意

    判断一个有向图是否有欧拉路径（一笔画），有就按字典序小输出，没有就输出 No

    思路

    欧拉路径：一笔画的路线

    按字典序小输出，先排序

    然后判断是否有欧拉路径，由于是有向图，所以判断方法为：[1]

    1. 起点和终点是同一点：所有点的出度与入度相等
    2. 起点和终点不是同一点：仅有一个点出度比入度多 11（起点），且仅有一个点入度比出度多 11（终点）

    不满足以上要求就没有欧拉路径，输出 No

    输出路径：见课件 P30[2]

    代码

    #include <bits/stdc++.h>
using namespace std;
const int N = 100005,M = 100005;
vector<int> a[N];
int e[N];	// 第 i 个点排到第几条边（在 a 里的）了
int ind[N],outd[N];
stack<int> s;
void dfs(int n){
	for (int i = e[n];i < a[n].size();i = e[n]){
		e[n] = i + 1;
		dfs(a[n][i]);
	}
	s.push(n);
}
int main(int argc, char **argv){
	int n,m;
	cin >> n >> m;
	for (int i = 0;i < m;i++){
		int u,v;
		cin >> u >> v;
		a[u].push_back(v);
		ind[v]++;
		outd[u]++;
	}
	// 判断是否为欧拉路
	int st = 1,stf(0),ef(0);bool f(0);
	for (int i = 1;i <= n;i++){
		if (ind[i] != outd[i]){
			f = 1;
			// 出度多 1，起点
			if (ind[i] == outd[i] - 1)		stf++,st = i;
			// 入度多 1，终点
			else if (ind[i] - 1 == outd[i])	ef++;
			else{
				printf("No");
				return 0;
			}
		}
	}
	if (f/*欧拉回路*/ && (stf != 1 && ef != 1)/*欧拉通路*/){
		printf("No");
		return 0;
	}

	// 字典序
	for(int i = 1;i <= n;i++){
		sort(a[i].begin(),a[i].end());
	}
	dfs(st);
	while(!s.empty()){
		printf("%d ",s.top());
		s.pop();
	}
	return 0;
}

    参考与鸣谢

    参考了洛谷大佬Marsrayd的这篇题解

    参考了老师的课件

    1. 详见课件 P25 ↩︎

    2. 课件 P30 ↩︎

    • @ 2024-6-7 21:17:11 
      #include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#define N 114514
#define M (2*N)
using namespace std;
int n,m,st=1;
int f=0,stf=0,ef=0;
vector<int>g[N];
int ind[N];
int oud[N];
int e[N];
stack<int>s;
void dfs(int x)
{
    for(int i=e[x];i<g[x].size();i=e[x])
    {
        e[x]=i+1;
        dfs(g[x][i]);
    }
    s.push(x);
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        ind[v]++;
        oud[u]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(ind[i]!=oud[i])
        {
            f=1;
            if(ind[i]==oud[i]-1)
            {
                stf++;
                st=i;
            }
            else if(ind[i]-1==oud[i])
            {
                ef++;
            }
            else
            {
                cout<<"No";
                return 0;
            }
        }
    }
    if(f && (stf!=1 && ef!=1))
    {
        cout<<"No";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        sort(g[i].begin(),g[i].end());
    }
    dfs(st);
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        
        s.pop();
    }
    return 0;
}
    • @ 2024-6-7 21:18:55

      #include #include #include #define N 114514 #define MOD 80112002 using namespace std; int n,m,sum=0; int ind[N]; int oud[N]; int cnt[N]; vectorg[N]; queueq; void topo() { for(int i=1;i<=n;i++) if(!ind[i]) { q.push(i); cnt[i]++; } while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<(int)g[u].size();i++) { int v=g[u][i]; cnt[v]+=cnt[u]; cnt[v]%=MOD; if(--ind[v]==0) { q.push(v); } } } } int main() { cin>>n>>m; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; g[b].push_back(a); ind[a]++; oud[b]++; } topo(); for(int i=1;i<=n;i++) { if(!oud[i]) { sum+=cnt[i]; sum%=MOD; } } cout<<sum; return 0; }

  • 5
    @ 2024-6-7 21:27:31 
    #include<bits/stdc++.h> 
using namespace std;
vector<int>g[200001];
int dr[200001];
int dc[200001];
stack<int>q;
int vis[200001];
void ol(int a){
	int sz=g[a].size();
	for(int i=vis[a];i<sz;i=vis[a]){
		vis[a]=i+1;
		ol(g[a][i]);
	}
	q.push(a);
}
int u[200001];
int v[200001];
int main(){
	int n,m,s=1,r1=0,r2=0,f=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u1,v1;
		cin>>u1>>v1;
		u[i]=u1;
		v[i]=v1;
		dc[u1]++;
		dr[v1]++;
		g[u1].push_back(v1);
	}
	for(int i=1;i<=n;i++){
		sort(g[i].begin(),g[i].end());
	}
	for(int i=1;i<=n;i++){
		if(dc[i]-dr[i]==1){
			s=i;
			break;
		}
	}
	for(int i=1;i<=n;i++){
		if(dr[i]-dc[i]==1){
			r1++;
			if(r1>1){
				cout<<"No";
				return 0;
			}
			else{
				continue;
			}
		}
		if(dc[i]-dr[i]==1){
		   r2++;
		   if(r2>1){
				cout<<"No";
				return 0;
			}
			else{
				continue;
			}	
		}
		if(dc[i]!=dr[i]){
			f=1;
		}
	}
	if(f==1){
		cout<<"No";
		return 0;
	}
	ol(s);
	while(!q.empty()){
		cout<<q.top()<<" ";
		q.pop();
	}
}
    • -1
      @ 2024-6-7 21:07:44

      题意

      为了找到有向图中字典序最小 初始化一些全局变量，包括访问标记数组 vis、邻接表 G、入度数组 ru、最近访问位置数组 newest 和一个栈 ans 用于存储最终的欧拉路径。

      读取输入，建立有向图的邻接表表示，并计算每个节点的入度。

      检查图中是否存在欧拉路径的条件：所有节点的入度和出度之差为0或1，且只有一个节点的入度和出度之差为1（起始点），只有一个节点的入度和出度之差为-1（结束点）。如果不满足这些条件，则输出 "No" 并返回。

      找到一个可能的起始点（即入度比出度少1的节点），如果没有这样的节点，则从任意节点开始。

      使用深度优先搜索（DFS）遍历图，同时在遍历时记录访问过的边的位置，以便回溯时可以继续未完成的遍历。

      在DFS过程中，每次访问完一个节点的所有邻居后，将该节点压入栈中。

      最后，如果找到了欧拉路径，则将栈中的元素依次弹出并输出，得到字典序最小的欧拉路径。

      请注意，这段代码假设输入的图是连通的，且满足欧拉路径存在的条件。如果图不连通或者不满足欧拉路径的条件 请修改 #何云锐置顶位#好评有置顶

      代码

      #include<bits/stdc++.h>
using namespace std;
int vis[100005]={0};
vector<int> G[100005];
int ru[100005]={0};
int newest[100005]={0};
stack<int> ans;
void dfs(int now)
{
    for(int next=newest[now];next<G[now].size();next=newest[now])
    {
        newest[now]=next+1;
        dfs(G[now][next]);
    }
    ans.push(now);
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        ru[y]++;
    }

    int start=1;
    int out=0,in=0;
    for(int i=1;i<=n;i++)
    {
        sort(G[i].begin(),G[i].end());
        int chu=G[i].size();
        if(chu-1==ru[i])
        {
            start=i;
            out++;
        }
        else if(ru[i]-1==chu)
        {
            in++;
        }
        else if(chu!=ru[i])
        {
            puts("No");
            return 0;
        }
        if(in>1||out>1)
        {
            puts("No");
            return 0;
        }
    }

    dfs(start);
    while(ans.size())
    {
        cout<<ans.top()<<" ";
        ans.pop();
    }
    return 0;
      • @ 2024-6-7 21:16:32

        👍

      • @ 2024-6-7 21:17:27 
        #include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#define N 114514
#define M (2*N)
using namespace std;
int n,m,st=1;
int f=0,stf=0,ef=0;
vector<int>g[N];
int ind[N];
int oud[N];
int e[N];
stack<int>s;
void dfs(int x)
{
    for(int i=e[x];i<g[x].size();i=e[x])
    {
        e[x]=i+1;
        dfs(g[x][i]);
    }
    s.push(x);
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        ind[v]++;
        oud[u]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(ind[i]!=oud[i])
        {
            f=1;
            if(ind[i]==oud[i]-1)
            {
                stf++;
                st=i;
            }
            else if(ind[i]-1==oud[i])
            {
                ef++;
            }
            else
            {
                cout<<"No";
                return 0;
            }
        }
    }
    if(f && (stf!=1 && ef!=1))
    {
        cout<<"No";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        sort(g[i].begin(),g[i].end());
    }
    dfs(st);
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        
        s.pop();
    }
    return 0;
}
      • @ 2024-6-7 21:19:05

        #include #include #include #define N 114514 #define MOD 80112002 using namespace std; int n,m,sum=0; int ind[N]; int oud[N]; int cnt[N]; vectorg[N]; queueq; void topo() { for(int i=1;i<=n;i++) if(!ind[i]) { q.push(i); cnt[i]++; } while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<(int)g[u].size();i++) { int v=g[u][i]; cnt[v]+=cnt[u]; cnt[v]%=MOD; if(--ind[v]==0) { q.push(v); } } } } int main() { cin>>n>>m; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; g[b].push_back(a); ind[a]++; oud[b]++; } topo(); for(int i=1;i<=n;i++) { if(!oud[i]) { sum+=cnt[i]; sum%=MOD; } } cout<<sum; return 0; }

      • @ 2024-6-7 21:19:14

        #include #include #include #define N 114514 #define MOD 80112002 using namespace std; int n,m,sum=0; int ind[N]; int oud[N]; int cnt[N]; vectorg[N]; queueq; void topo() { for(int i=1;i<=n;i++) if(!ind[i]) { q.push(i); cnt[i]++; } while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<(int)g[u].size();i++) { int v=g[u][i]; cnt[v]+=cnt[u]; cnt[v]%=MOD; if(--ind[v]==0) { q.push(v); } } } } int main() { cin>>n>>m; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; g[b].push_back(a); ind[a]++; oud[b]++; } topo(); for(int i=1;i<=n;i++) { if(!oud[i]) { sum+=cnt[i]; sum%=MOD; } } cout<<sum; return 0; }

    • 1

    【模板】欧拉路径

    Information

    ID
    1097
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    9
    Tags
    # Submissions
    69
    Accepted
    7
    Uploaded By
    1. About
    2. Contact Us
    3. Privacy
    4. Terms of Service
    5. Copyright Complaint
    6. Language
    7. Legacy mode
    8. Theme
    2. 粤ICP备2022044963号-1
    3. Worker 0, 25ms
    4. Powered by Hydro v4.13.3 Community