牛客练习赛25 E 定向

62 阅读 0 评论 41 点赞

我是靠谱客的博主高兴泥猴桃，最近开发中收集的这篇文章主要介绍牛客练习赛25 E 定向，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://www.nowcoder.com/acm/contest/158/E
来源：牛客网

定向

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

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

复制

输出

复制

说明

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

备注:

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

思路：图论的简单应用吧。只要图中有桥就一定是impossible，否则就可以。先找到桥边，去掉桥边以后进行一遍dfs定向即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define N 1500005
#define M 1500005
using namespace std;
namespace fastIO {
#define BUF_SIZE 100000
//fread -> read
bool IOerror = 0;
inline char nc() {
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
if(pend == p1) {
IOerror = 1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch == ' ' || ch == 'n' || ch == 'r' || ch == 't';
}
inline void read(int &x) {
char ch;
while(blank(ch = nc()));
if(IOerror) return;
for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
}
#undef BUF_SIZE
};
using namespace fastIO;
//
void read(int &x){scanf("%d",&x);}
int fg;
int n,m;//n个点 m条边
struct node
{
int from,to,nex;
int cut;//记录这条边是否为割边
}edge[2*M];//双向边则 edge[i]与edge[i^1]是2条反向边
int head[N] ,edgenum;//在一开始就要 memset(head,-1,sizeof(head)); edgenum=0;
int low[N],dfn[N],tarjin_time;
void add(int u,int v)
{
node E={u,v,head[u],0};
edge[edgenum]=E;
head[u]=edgenum++;
}
void tarjin(int u,int pre)
{
low[u]=dfn[u]= ++tarjin_time;
int flag=1;//flag是阻止双向边的反向边 i和i^1
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(flag&&v==pre)
{
flag=0;
continue;
}
if(!dfn[v])
{
tarjin(v,u);
if(low[u]>low[v])low[u]=low[v];
if(low[v]>dfn[u])//是桥low[v]表示v能走到的最早祖先 有重边且u是v的最早祖先 则low[v]==dfn[u],所以不会当作桥
{fg=1;edge[i].cut=edge[i^1].cut=true;}
}
else if(low[u]>dfn[v])low[u]=dfn[v];
}
}
bool liantong;//是否连通
void find_edgecut()
{
memset(dfn,0,sizeof(dfn));
tarjin_time=0;
tarjin(1,1);
liantong=true;
for(int i=1;i<=n;i++)if(!dfn[i]){liantong=false;return;}
}
bool vis[N];
void init(){
for(int i = 0;i<=n;i++)head[i] = -1;
edgenum = 0;
memset(vis, 0, sizeof(vis));
fg = 0;
}
void dfs(int u, int fa){
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nex){
int v = edge[i].to;
if( edge[i].cut == 1)continue;
if(edge[i^1].cut!=-1)edge[i].cut = -1;
if(!vis[v]) dfs(v, u);
}
}
int main(){
int u, v, Cas = 1;
read(n);read(m);{
init();
while(m--){
read(u);read(v);
add(u, v);
add(v, u);
}
find_edgecut();
for(int i = 1; i <= n; i++)if(!vis[i])dfs(i, i);
if(fg){puts("impossible");return 0;}
for(int i = 0; i < edgenum; i+=2)
if(edge[i].cut)printf("0");
else printf("1");
puts("");
}
return 0;
}