UESTC - 900 方老师炸弹 —— 割点

时间：2024-06-05 21:07:26

题目链接：https://vjudge.net/problem/UESTC-900

方老师炸弹

Time Limit: 4000/2000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit 
Status

方老师准炸毁学校,学校可以被看做是一个图包含NN个顶点和MM条边(顶点从00开始标号)，方老师发明了一个方老师炸弹。

这个炸弹可以炸毁某一个节点和与这个节点相连的所有边。但是方老师现在很彷徨，他想使得使用了一个炸弹之后学校炸成更多的联通块。

方老师想知道把学校炸成尽量多块的放置点的前KK个顶点是哪些，这些点可以被把学校炸成多少个联通块？

Input

  • 多组数据，EOF结束。
  • 第11行：NN和MM和KK
  • 第22到第M+1M+1行：每一行22个数UiUi和ViVi，表示UiUi到ViVi之间有一条边。

Output

KK行，每行22个数PosiPosi，CiCi，用空格隔开，表示在PosiPosi点放置炸弹可以把学校炸成CiCi块。如果对于不同的点可以把学校炸成相同多块，优先输出编号小的顶点。

每组数据后面输出一个空行

Sample input and output

Sample Input Sample Output 
8 8 4

0 4

1 2

2 3

2 4

3 5

3 6

3 7

6 7
 
2 3

3 3

4 2

0 1

Hint

K≤N≤10000K≤N≤10000，M≤100000







题解：

割点的裸题。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int maxn = +;

 int n, m, k,vis[maxn], low[maxn], dfn[maxn], stamp;

 struct node //q[i].x为删除结点i后增加的连通块

 {

     int x, id;

     bool operator<(const node &a)const{

         if(x==a.x) return id<a.id;

         return x>a.x;

     }

 }q[maxn];

 struct

 {

     int v, next;

 }edge[maxn*];

 int tot, head[maxn];

 void add(int u, int v)

 {

     edge[tot].v = v;

     edge[tot].next = head[u];

     head[u] = tot++;

 }

 void dfs(int u, int pre)

 {

     dfn[u] = low[u] = ++stamp;

     for(int i = head[u]; i!=-; i = edge[i].next)

     {

         int v = edge[i].v;

         if(v==pre) continue;

         if(!dfn[v])

         {

             dfs(v, u);

             low[u] = min(low[u], low[v]);

             if(low[v]>=dfn[u])

                 q[u].x++;

         }

         else

             low[u] = min(low[u],dfn[v]);

     }

 }

 int main()

 {

     while(scanf("%d%d%d",&n,&m,&k)!=EOF)

     {

         memset(vis,, sizeof(vis));

         memset(low,, sizeof(low));

         memset(dfn,, sizeof(dfn));

         memset(head,-, sizeof(head));

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

         {

             q[i].x = ;

             q[i].id = i;

         }

         q[].x = ;

         tot = ;

         for(int i = ; i<m; i++)

         {

             int u, v;

             scanf("%d%d",&u,&v);

             add(u,v);

             add(v,u);

         }

         stamp = ;

         dfs(,-);

         sort(q, q+n);

         for(int i = ; i<k; i++)

             printf("%d %d\n",q[i].id, q[i].x);

         putchar('\n');

     }

 }

相关文章