HDU 5876:Sparse Graph(BFS)

时间:2022-09-05 18:16:05

http://acm.hdu.edu.cn/showproblem.php?pid=5876

Sparse Graph

Problem Description
 
In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Now you are given an undirected graph G of N nodes and M bidirectional edges of unit length. Consider the complement of G, i.e., H. For a given vertex S on H, you are required to compute the shortest distances from S to all N−1 other vertices.

 
Input
 
There are multiple test cases. The first line of input is an integer T(1≤T<35) denoting the number of test cases. For each test case, the first line contains two integers N(2≤N≤200000) and M(0≤M≤20000). The following M lines each contains two distinct integers u,v(1≤u,v≤N) denoting an edge. And S (1≤S≤N) is given on the last line.
 
Output
 
For each of T test cases, print a single line consisting of N−1 space separated integers, denoting shortest distances of the remaining N−1 vertices from S (if a vertex cannot be reached from S, output ``-1" (without quotes) instead) in ascending order of vertex number.
 
Sample Input
 
1
2 0
1
 
Sample Output
 
1

题意:给出一个图,和一个起点,求在该图的补图中从起点到其他N-1个点的最短距离。如果不连通输出-1.

思路:比赛的时候觉得这题N那么大不会做。现在回过头发现貌似不难。用set将未走过的点放置进去,并在对点的邻边进行扩展的时候,把能走到的邻点删除掉(即补图中可以走到的邻点保留)。

 #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
using namespace std;
#define N 200010
#define INF 0x3f3f3f3f struct node
{
int v, nxt;
}edge[N];
int head[N];
int d[N], tot; void add(int u, int v)
{
edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot++;
edge[tot].v = u; edge[tot].nxt = head[v]; head[v] = tot++;
} void bfs(int st, int n)
{
queue<int> que;
d[st] = ;
que.push(st);
set<int> s1, s2;
for(int i = ; i <= n; i++) {
if(i != st) s1.insert(i);
}
while(!que.empty()) {
int u = que.front(); que.pop();
for(int k = head[u]; ~k; k = edge[k].nxt) {
int v = edge[k].v;
if(!s1.count(v)) continue;
s1.erase(v); //补图中当前能走到的并且还未更新过的
s2.insert(v); //补图中走不到的还要扩展的
}
for(set<int>:: iterator it = s1.begin(); it != s1.end(); it++) {
d[*it] = d[u] + ;
que.push(*it);
}
s1.swap(s2); //还没更新过的
s2.clear();
}
} int main()
{
int t;
scanf("%d", &t);
while(t--) {
memset(head, -, sizeof(head));
memset(d, INF, sizeof(INF));
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
int st;
scanf("%d", &st);
bfs(st, n);
bool f = ;
for(int i = ; i <= n; i++) {
if(i != st) {
if(f) printf(" ");
f = ;
if(d[i] == INF) printf("-1");
else printf("%d", d[i]);
}
}
puts("");
} return ;
}

HDU 5876:Sparse Graph(BFS)的更多相关文章

  1. HDU - 5876 :Sparse Graph (完全图的补图的最短路 -BFS&amp&semi;set)

    In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinc ...

  2. HDU 1728:逃离迷宫(BFS)

    http://acm.hdu.edu.cn/showproblem.php?pid=1728 逃离迷宫 Problem Description   给定一个m × n (m行, n列)的迷宫,迷宫中有 ...

  3. HDU&period;2612 Find a way (BFS)

    HDU.2612 Find a way (BFS) 题意分析 圣诞节要到了,坤神和瑞瑞这对基佬想一起去召唤师大峡谷开开车.百度地图一下,发现周围的召唤师大峡谷还不少,这对基佬纠结着,该去哪一个...坤 ...

  4. HDU 4635:Strongly connected(强连通)

    http://acm.hdu.edu.cn/showproblem.php?pid=4635 题意:给出n个点和m条边,问最多能添加几条边使得图不是一个强连通图.如果一开始强连通就-1.思路:把图分成 ...

  5. 九度OJ 1335:闯迷宫 (BFS)

    时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:1782 解决:483 题目描述: sun所在学校每年都要举行电脑节,今年电脑节有一个新的趣味比赛项目叫做闯迷宫. sun的室友在帮电脑节设计 ...

  6. 题解报告:hdu 2717 Catch That Cow(bfs)

    Problem Description Farmer John has been informed of the location of a fugitive cow and wants to cat ...

  7. HDU 2717 Catch That Cow (bfs)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2717 Catch That Cow Time Limit: 5000/2000 MS (Java/Ot ...

  8. HDU 1890:Robotic Sort(Splay)

    http://acm.hdu.edu.cn/showproblem.php?pid=1890 题意:有一个无序序列,经过不断地翻转,使得最后的序列是一个升序的序列,而且如果相同数字要使在原本序列靠前的 ...

  9. HDU 2767:Proving Equivalences(强连通)

    http://acm.hdu.edu.cn/showproblem.php?pid=2767 题意:给出n个点m条边,问在m条边的基础上,最小再添加多少条边可以让图变成强连通.思路:强连通分量缩点后找 ...

随机推荐

  1. Angular指令渗透式理解

    通过一段时间对angular指令的使用,理解了angular指令的意义,下面逐一介绍一下. ng-app:定义一个angualr模块,表示angular作用的范围,如下代码: ng-app在html标 ...

  2. I2C总线模拟(郭天祥视屏)

    电路图 思路 1.向EEPROM中通过I2C总线写入一个字节 2.通过I2C总线读出写入的字节 3.如果写入和读出成功点亮发光二极管 程序 #include <REGX51.H> #def ...

  3. python3之异常处理,断言和反射

    1.异常基础 python在运行过程中,程序解释机制会测试代码,如检测不通过则会抛出异常. try: aa = 10 bb = ' cc = aa + bb except Exception as e ...

  4. Linux以GB显示内存大小

    Linux以GB显示内存大小 youhaidong@youhaidong-ThinkPad-Edge-E545:~$ free -g total used free shared buffers ca ...

  5. struts2 可以用ognl拿到值而不可以用el拿到值的解决方法

    错误debug后 得到了There is no read method for container的错误 于是我new了一个实体类 package com.unity; public class St ...

  6. css的overflow属性

    原文:https://www.jianshu.com/p/67b536fc67c1 ------------------------------------------- 事实上我挺长一段时间都没弄清 ...

  7. Linux实现多线程高速下载

    使用Wget下载,有时候速度挺慢的. 有没有好办法呢? 一.解决方案 安装axel 安装方法: yum -y install epel-release .el7.x86_64.rpm rpm -ivh ...

  8. express session

    一.什么是session? 最近在学习node.js 的express框架,接触到了关于session方面的内容.翻阅了一些的博客,学到了不少东西,发现一篇博文讲的很好,概念内容摘抄如下: Sessi ...

  9. Maven Compilation error &lbrack;package org&period;testng&period;annotations does not exist&rsqb;

    背景 在执行mvn test的时候,提示package org.testng.annotations does not exist 解决办法 Open pom.xml file. Go to &quo ...

  10. 按位与&amp&semi;、按位或&vert;、按位异或&Hat;

    与1进行位与&运算,值保持不变: 与0进行位与&运算,值清0: 按位与&常用于将整型变量中某些位清0,而其他位保持不变. 与1进行位或|运算,值置1: 与0进行位或|运算,值保 ...