最近好懒,堆了好多题没写题解。。
原题链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1706
题意:
给你一个图,问你每个点去掉后有多少个联通块
题解:
就Tarjan一下就好,很简单
代码:
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<cstdio>
#include<string>
#include<algorithm>
#define MAX_N 11234
using namespace std; int n,m;
vector<int> G[MAX_N]; int dfn[MAX_N],low[MAX_N],ind=;
bool vis[MAX_N]; struct node{
public:
int pos,val;
void print(){
cout<<pos-<<" "<<val<<endl;
}
}; bool cmp(node a,node b){
if(a.val==b.val)return a.pos<b.pos;
return a.val>b.val;
} node d[MAX_N]; void Tarjan(int u,int p){
d[u].pos=u,d[u].val=;
dfn[u]=low[u]=++ind;
vis[u]=;
int child=;
for(int i=;i<G[u].size();i++){
int v=G[u][i];
if(v==p)continue;
if(!vis[v]){
child++;
Tarjan(v,u);
low[u]=min(low[v],low[u]);
if(low[v]>=dfn[u]&&p!=)d[u].val++;
}
else low[u]=min(dfn[v],low[u]);
}
if(p==&&child>)d[u].val=child;
} void init(){
memset(vis,,sizeof(vis));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
ind=;
for(int i=;i<=n;i++)G[i].clear();
} int main(){
cin.sync_with_stdio(false);
while(true){
cin>>n>>m;
if(n==&&m==)break;
init();
while(true){
int u,v;
cin>>u>>v;
if(u==-)break;
u++;v++;
G[u].push_back(v);
G[v].push_back(u);
}
Tarjan(,);
sort(d+,d++n,cmp);
for(int i=;i<=m;i++)
d[i].print();
cout<<endl;
}
return ;
}