fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n,m,k;
  5. vector<int>vr[3001];
  6.  
  7. bool isvisited[3001],Ap[3001];
  8. int parent[3001];
  9.  
  10. int low[3001],disc[3001];
  11.  
  12.  
  13. int ti=0;
  14. void dfs(int v){
  15. 	isvisited[v]=true;
  16. 	low[v]=disc[v]=ti;
  17. 	ti++;
  18. 	int child=0;
  19. 	for(int i=0;i<vr[v].size();i++){
  20. 		if(parent[v]==vr[v][i]) continue;
  21. 		if(!isvisited[vr[v][i]]){
  22. 			child++;
  23. 			parent[vr[v][i]]=v;
  24. 			dfs(vr[v][i]);
  25. 			low[v]=min(low[v],low[vr[v][i]]);
  26. 			if(parent[v]==-1 && child>1){
  27. 				Ap[v]=true;
  28. 			}
  29. 			if(parent[v]!=-1 && low[vr[v][i]]>=disc[v]){
  30. 				Ap[v]=true;
  31. 			}
  32. 		}
  33. 		else if(parent[v]!=vr[v][i]){
  34. 			low[v]=min(low[v],disc[vr[v][i]]);
  35. 		}
  36.  
  37. 	}
  38. 	return;
  39. }
  40.  
  41. int main(){
  42. 	int t;
  43. 	cin>>t;
  44. 	while(t--){
  45. 		cin>>n>>m>>k;
  46. 		int a,b;
  47. 		ti=0;
  48. 		int ans=0;
  49. 		for(int i=0;i<n;i++)
  50. 		{
  51. 			low[i]=disc[i]=0;
  52.  
  53. 			Ap[i]=false;
  54. 			isvisited[i]=false;
  55. 			vr[i].clear();
  56. 		}
  57. 		parent[0]=-1;
  58. 		for(int i=0;i<m;i++){
  59. 			cin>>a>>b;
  60. 			vr[a].push_back(b);
  61. 			vr[b].push_back(a);
  62. 		}
  63. 		dfs(0);
  64. 		for(int i=0;i<n;i++){
  65. 			if(Ap[i]){
  66. 				ans+=k;
  67. 			}
  68. 		}
  69. 		cout<<ans<<endl;
  70. 	}
  71. }
Success #stdin #stdout 0s 16176KB
comments (?)
stdin
copy 
1
7 6 5
0 1
1 2
3 4
2 4
2 6
5 2
stdout
copy 
15
https://ideone.com/zPd82e
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!