HDU 5876 Sparse Graph BFS+set删点

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个点的完全图，再给你m条边需要删除，给定s，问s到其他所有点的距离 \\(2\le N\le 200000 \\) \\(0\le M\le 20000\\)
**思路：**因为边权值为1，所以直接BFS，再者就是考虑如何枚举点了，用vis标记的话，时间会不够（TLE了一发），在这里使用set维护点集（多方便）但是要注意把点从集合中去除时，不能直接边遍历边去，而是一遍遍历完一起去掉，因为使用的迭代器地址不会随删除而改变...

/** @Date    : 2016-11-14-17.20


  * @Author  : Lweleth (SoungEarlf@gmail.com)


  * @Link    : https://github.com/


  * @Version :


  */


#include <stdio.h>


#include <iostream>


#include <string.h>


#include <algorithm>


#include <utility>


#include <vector>


#include <map>


#include <set>


#include <string>


#include <stack>


#include <queue>


#define pii pair<int , int>


#define MP(x, y) make_pair((x) ,(y))


#define ff first


#define ss second


#define LL long long


#define MMF(x) memset((x),0,sizeof(x))


#define MMI(x) memset((x), INF, sizeof(x))


using namespace std;





const int INF = 0x3f3f3f3f;


const int N = 2e5+20;





map<pii ,bool>mp;


set<int>st;


set<int>::iterator it;


int res[N];


int n, m;


void bfs(int s,int n)


{


    queue<int>q, t;





    res[s] = 0;


    q.push(s);





    st.erase(s);


    while(!q.empty())


    {


        int nw = q.front();


        //cout << nw;


        q.pop();


        for(it = st.begin(); it != st.end(); it++)


        {


            //cout << "~"<< *it << " " ;


            if(!mp[MP(nw, *it)])


            {


                res[*it] = res[nw] + 1;


                q.push(*it);


                t.push(*it);


                //st.erase(*it);//不能直接删会有问题


                //if(st.empty())


                    //break;





            }


        }


        while(!t.empty())


        {


            int x = t.front();


            t.pop();


            st.erase(x);


        }


        //cout << endl;


    }





}





int main()


{





    int T;


    while(~scanf("%d", &T))


    {


        while(T--)


        {


            mp.clear();


            st.clear();


            scanf("%d%d", &n, &m);





            for(int i = 1; i <= n; i++)


                st.insert(i);





            while(m--)


            {


                int x, y;


                scanf("%d%d", &x, &y);


                mp[MP(x, y)] = mp[MP(y, x)] = 1;


            }





            int s;


            scanf("%d", &s);


            bfs(s, n);


            ////


            int flag = 0;


            for(int i = 1; i <= n; i++)


            {


                if(i != s)


                {


                    if(flag)


                        printf(" ");


                    if(res[i] != 0)


                        printf("%d", res[i]);


                    else printf("-1");


                    flag = 1;


                }


            }


            printf("\n");


        }











    }


    return 0;


}


/*


99


6 9


1 3


1 4


2 3


2 4


2 5


3 5


3 6


4 6


5 6


1


*/

巴特西

HDU 5876 Sparse Graph BFS+set删点

最新文章

热门文章