牛客练习赛25—E定向

77 阅读 0 评论 51 点赞

我是靠谱客的博主激情大雁，这篇文章主要介绍牛客练习赛25—E定向，现在分享给大家，希望可以做个参考。

题目链接：传送门

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

给一张无向图，你需要将边定向，使得定向后的有向图强连通。

输入描述:

复制代码

1
2
第一行两个数n,m，表示点数和边数。
接下来m行，每个两个数x,y，表示x和y之间有条边。

输出描述:

复制代码

1
2
3
如果不存在可行方案输出一行"impossible" ；
否则，输出一个长度为m的01串，描述你的方案，
第i个字符为1表示输入的第i条边定向为从x到y，为0表示从y到x。

示例1

输入

复制

复制代码

输出

复制

复制代码

1
101

说明

复制代码

1
1->2->3->1，形成一个环 ，是强连通的。

备注:

复制代码

1
1 ≤ n,m ≤ 106 ，保证无重边自环

解题思路：

dfs建立一颗树，所有树边从父亲指向儿子，返祖边从后代指向祖先。

假如这是一个联通图，且没有割边，那么祖先结点总能到达后代结点，而后代结点也能通过返祖边到达祖先结点。

所以只要图联通，且没有割边那么一定有解。

代码：

复制代码

#include <bits/stdc++.h>
using namespace std;
typedef long long llt;
const int INF = 0x3fffffff;
const int N = 1000010;
const int M = 100010;
const double pi = acos(-1);
const int mod = 1e9+7;
struct Edge{
int u,id,dir;
Edge*next;
}edge[N];
int Ecnt,cnt,val,low[N],dfn[N],e[N];
Edge*head[N];
void init()
{
Ecnt = cnt = val = 0;
fill(head,head+N,(Edge*)0);
}
void mkEdge(int a,int b,int id,int dir)
{
edge[Ecnt].u = b;
edge[Ecnt].id = id;
edge[Ecnt].dir = dir;
edge[Ecnt].next = head[a];
head[a] = edge+Ecnt++;
}
void dfs(int u,int fa)
{
low[u] = dfn[u] = ++cnt;
for(Edge*p = head[u]; p; p = p->next){
int v = p->u;
if(v == fa) continue;
//cout << u << " " << v << " " << p->dir << endl;
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u]) val++;
e[p->id] = p->dir;
}else{
low[u] = min(low[u],dfn[v]);
if(dfn[v] < dfn[u])
e[p->id] = p->dir;
}
}
}
int main()
{
init();
int n,m,a,b;
scanf("%d%d",&n,&m);
for(int i = 0; i < m; ++i){
scanf("%d%d",&a,&b);
mkEdge(a,b,i,1);
mkEdge(b,a,i,0);
}
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
dfs(1,-1);
if(cnt != n || val != 0) printf("impossiblen");
else{
for(int i = 0; i < m; ++i){
printf("%d",e[i]);
}
printf("n");
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
typedef long long llt;
const int INF = 0x3fffffff;
const int N = 1000010;
const int M = 100010;
const double pi = acos(-1);
const int mod = 1e9+7;
struct Edge{
int u,id,dir;
Edge*next;
}edge[N];
int Ecnt,cnt,val,low[N],dfn[N],e[N];
Edge*head[N];
void init()
{
Ecnt = cnt = val = 0;
fill(head,head+N,(Edge*)0);
}
void mkEdge(int a,int b,int id,int dir)
{
edge[Ecnt].u = b;
edge[Ecnt].id = id;
edge[Ecnt].dir = dir;
edge[Ecnt].next = head[a];
head[a] = edge+Ecnt++;
}
void dfs(int u,int fa)
{
low[u] = dfn[u] = ++cnt;
for(Edge*p = head[u]; p; p = p->next){
int v = p->u;
if(v == fa) continue;
//cout << u << " " << v << " " << p->dir << endl;
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u]) val++;
e[p->id] = p->dir;
}else{
low[u] = min(low[u],dfn[v]);
if(dfn[v] < dfn[u])
e[p->id] = p->dir;
}
}
}
int main()
{
init();
int n,m,a,b;
scanf("%d%d",&n,&m);
for(int i = 0; i < m; ++i){
scanf("%d%d",&a,&b);
mkEdge(a,b,i,1);
mkEdge(b,a,i,0);
}
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
dfs(1,-1);
if(cnt != n || val != 0) printf("impossiblen");
else{
for(int i = 0; i < m; ++i){
printf("%d",e[i]);
}
printf("n");
}
return 0;
}