首页 > 代码库 > HDU 5876：Sparse Graph（BFS）

HDU 5876：Sparse Graph（BFS）

2024-08-13 01:37:57   221人阅读

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将未走过的点放置进去，并在对点的邻边进行扩展的时候，把能走到的邻点删除掉（即补图中可以走到的邻点保留）。

 1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <queue> 8 #include <vector> 9 #include <set>10 using namespace std;11 #define N 20001012 #define INF 0x3f3f3f3f13 14 struct node15 {16     int v, nxt;17 }edge[N];18 int head[N];19 int d[N], tot;20 21 void add(int u, int v)22 {23     edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot++;24     edge[tot].v = u; edge[tot].nxt = head[v]; head[v] = tot++;25 }26 27 void bfs(int st, int n)28 {29     queue<int> que;30     d[st] = 0;31     que.push(st);32     set<int> s1, s2;33     for(int i = 1; i <= n; i++) {34         if(i != st) s1.insert(i);35     }36     while(!que.empty()) {37         int u = que.front(); que.pop();38         for(int k = head[u]; ~k; k = edge[k].nxt) {39             int v = edge[k].v;40             if(!s1.count(v)) continue;41             s1.erase(v); //补图中当前能走到的并且还未更新过的42             s2.insert(v); //补图中走不到的还要扩展的43         }44         for(set<int>:: iterator it = s1.begin(); it != s1.end(); it++) {45             d[*it] = d[u] + 1;46             que.push(*it);47         }48         s1.swap(s2); //还没更新过的49         s2.clear();50     }51 }52 53 int main()54 {55     int t;56     scanf("%d", &t);57     while(t--) {58         memset(head, -1, sizeof(head));59         memset(d, INF, sizeof(INF));60         int n, m;61         scanf("%d%d", &n, &m);62         for(int i = 0; i < m; i++) {63             int u, v;64             scanf("%d%d", &u, &v);65             add(u, v);66         }67         int st;68         scanf("%d", &st);69         bfs(st, n);70         bool f = 0;71         for(int i = 1; i <= n; i++) {72             if(i != st) {73                 if(f) printf(" ");74                 f = 1;75                 if(d[i] == INF) printf("-1");76                 else printf("%d", d[i]);77             }78         }79         puts("");80     }81 82     return 0;83 }

 

HDU 5876：Sparse Graph（BFS）


联系
我们