牛客练习赛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。
【牛客练习赛25 E 定向】示例1
输入 复制
3 3 1 2 1 3 2 3
输出 复制
101
说明
1->2->3->1,形成一个环 ,是强连通的。
备注:
1 ≤ n,m ≤ 106 ,保证无重边自环
思路:图论的简单应用吧。只要图中有桥就一定是impossible,否则就可以。先找到桥边,去掉桥边以后进行一遍dfs定向即可。
代码:
#include
#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;
}
推荐阅读
- 牛客网Wannafly挑战赛25|牛客网Wannafly挑战赛25 A题
- 牛客练习赛3|牛客练习赛3 B - 贝伦卡斯泰露
- 牛客网_Wannafly模拟赛1
- 头部协议,网页描述,关键字,重定向,加载css|头部协议,网页描述,关键字,重定向,加载css,js
- #|牛客算法题——NC15553 数学考试【所用算法(前缀和】)
- 牛客算法周周练15——A、B
- 前后缀和|牛客小白月赛5 I.区间 (interval)
- 12/18
- 牛客 C. 子段乘积(线段树)
- 牛客挑战赛39 C 牛牛的等差数列(线段树)(*)