RouterMesh

NC211810. RouterMesh

描述

In a Mesh networking system, there are $n_{}$ MI Routers, where $m_{}$ pairs of MI Routers are bidirectionally connected. In order to check the stability of the system, for each MI Router, we should determine the number of connected components after removing it and relative connections from the system. And then assess that if we should add more MI Routers into the system. Print the numbers of connected components in residual system after removing each MI Router.

输入描述

The first line contains two integers , denoting the number of MI Routers and bidirectional connections in the Mesh networking system.

Following  lines each contains two integers , denoting the -th MI Router has a bidirectional connection with the -th MI Router.

It's guaranteed that there are no duplicated connections in input.

输出描述

Print one line containing  integers, where -th integer denotes the number of connected components after removing -th MI Router and relative connections.

示例1

输入:

4 2
1 2
1 3

输出:

3 2 2 1

说明:

After removing the 1st MI Router and relative connections, there are $3_{}$ connected components: $\{2\}, \{3\}, \{4\}_{}$ .
After removing the 2nd MI Router and relative connections, there are $2_{}$ connected components: $\{1, 3\}, \{4\}_{}$ .
After removing the 3rd MI Router and relative connections, there are $2_{}$ connected components: $\{1, 2\}, \{4\}_{}$ .
After removing the 4th MI Router and relative connections, there is only $1_{}$ connected component: $\{1, 2, 3\}_{}$ .

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 267ms, 内存消耗: 29584K, 提交时间: 2020-10-31 09:49:19

#include<bits/stdc++.h>
const int _=3e5+5;
using namespace std;
int ans,n,m,cnt,dfn[_],low[_],f[_],g[_];
vector<int>vec[_];
void dfs(int fa,int u){
	if(dfn[u])return ;
	dfn[u]=low[u]=++cnt;  
	for(int i=0,l=vec[u].size();i<l;++i){
		int v=vec[u][i]; if(dfn[v]){low[u]=min(low[u],dfn[v]);continue;}
		dfs(u,v); if(dfn[u]<=low[v])++f[u];
		low[u]=min(low[u],low[v]);
	}
	if(fa==0)--f[u]; 
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i])dfs(0,i),++ans;
	for(int i=1;i<=n;++i)
		cout<<f[i]+ans<<" ";
	cout<<endl;
	return 0;
}

上一题

下一题

详情