题意:
给了一个联通无向图...现在问去掉某个点..会让图变成几个联通块?...输出的..按分出的从多到小..若相等..输出标号从小到大.输出M个...
题解:
从求割点的过程演变得出一个点去掉会将图变成几个联通块..
也就是在做tarjan时...当一个边dfn[u]<=low[v]时..其分成的块个数++..但值得注意的同样是一个联通快第一个进去的点.个数要-1...
Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<set> #include <stack> #include<queue> #include<algorithm> #include<cmath> #define oo 1000000007 #define ll long long #define pi acos(-1.0) #define MAXN 10005 #define MAXM 500505 using namespace std; struct node { int v,u,id,next; }edge[MAXM]; struct NODE { int id,num; }ans[MAXN]; int Ne,_next[MAXN],dfn[MAXN],DfsIndex,low[MAXN]; set<int> Ans[MAXN]; void addedge(int u,int v,int id) { edge[++Ne].next=_next[u],_next[u]=Ne; edge[Ne].u=u,edge[Ne].v=v,edge[Ne].id=id; } void tarjan(int u,int id) { dfn[u]=low[u]=++DfsIndex; ans[u].id=u,ans[u].num=1; for (int k=_next[u];k;k=edge[k].next) if (edge[k].id!=id) { int v=edge[k].v; if (!dfn[v]) { tarjan(v,edge[k].id); low[u]=min(low[u],low[v]); if (dfn[u]<=low[v]) ans[u].num++; }else low[u]=min(low[u],dfn[v]); } } bool cmp(NODE a,NODE b) { if (a.num!=b.num) return a.num>b.num; return a.id<b.id; } int main() { int u,v,n,m,id,i; while (scanf("%d%d",&n,&m) && n && m) { Ne=id=0,memset(_next,0,sizeof(_next)); while (scanf("%d%d",&u,&v) && u!=-1) addedge(u,v,++id),addedge(v,u,id); memset(dfn,0,sizeof(dfn)); DfsIndex=0; for (u=0;u<n;u++) if (!dfn[u]) { tarjan(u,0); ans[u].num--; } sort(ans,ans+n,cmp); for (i=0;i<m;i++) printf("%d %d\n",ans[i].id,ans[i].num); puts(""); } return 0; }