fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. #include<unistd.h>
  4. using namespace std;
  5.  
  6.  
  7. typedef long long int lint;
  8. typedef pair<int,int> pi;
  9.  
  10. const int N=100005,M=100005,Q=100005;
  11. struct uf{
  12.  
  13. 	static const int MAXN=2*M;
  14. 	int par[MAXN];
  15. 	int size[MAXN];
  16. 	void init(){
  17. 		memset(par,-1,sizeof(par));
  18. 		for(int i=0;i<MAXN;++i) size[i]=1;
  19. 	}
  20. 	int root(int a){
  21. 		if(par[a]==-1) return a;
  22. 		return par[a]=root(par[a]);
  23. 	}
  24. 	void unite(int a,int b){
  25. 		a=root(a);b=root(b);
  26. 		if(a==b) return;
  27. 		if(size[a]<size[b]) swap(a,b);
  28.  
  29. 		par[b]=a;
  30. 		size[a]+=size[b];
  31. 	}
  32. 	bool same(int a,int b){
  33. 		return root(a)==root(b);
  34. 	}
  35. };
  36.  
  37. uf u;
  38.  
  39. int n,m,q;
  40.  
  41. vector<int> adjcol[N];
  42. pair<pi,int> es[M];
  43. int degsum[N];
  44.  
  45. int getpos(const vector<int>& ar,int indx,int c){
  46. 	return degsum[indx]+lower_bound(ar.begin(),ar.end(),c)-ar.begin();
  47. }
  48. int main(){
  49. 	cin>>n>>m;
  50. 	for(int i=0;i<m;++i){
  51. 		int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b;
  52. 		adjcol[a].push_back(c);
  53. 		adjcol[b].push_back(c);
  54.  
  55. 		es[i]=make_pair(make_pair(a,b),c);
  56. 	}
  57.  
  58. 	for(int i=0;i<n;++i){
  59. 		sort(adjcol[i].begin(),adjcol[i].end());
  60. 		adjcol[i].erase(unique(adjcol[i].begin(),adjcol[i].end()),adjcol[i].end());
  61. 		degsum[i+1]=degsum[i]+adjcol[i].size();
  62. 	}
  63. 	u.init();
  64. 	for(int i=0;i<m;++i){
  65. 		int a=es[i].first.first,b=es[i].first.second,c=es[i].second;
  66. 		int A=getpos(adjcol[a],a,c),B=getpos(adjcol[b],b,c);
  67. 		u.unite(A,B);
  68. 	}
  69.  
  70. 	int q;cin>>q;
  71.  
  72. 	map<pi,int> memo;
  73. 	for(int qcnt=0;qcnt<q;++qcnt){
  74. 		int a,b;scanf("%d%d",&a,&b);--a;--b;
  75. 		int res=0;
  76. 		if(adjcol[a].size()>adjcol[b].size()){
  77. 			swap(a,b);
  78. 		}
  79.  
  80. 		pi p=make_pair(a,b);
  81. 		if(memo.count(p)){
  82. 			res=memo[p];
  83. 		}else{
  84. 			for(int i=0;i<adjcol[a].size();++i){
  85. 				int c=adjcol[a][i];
  86. 				if(binary_search(adjcol[b].begin(),adjcol[b].end(),c)){
  87. 					int trg=getpos(adjcol[b],b,c);
  88. 					if(u.same(trg,degsum[a]+i)){
  89. 						++res;
  90. 					}
  91. 				}
  92. 			}
  93. 			memo[p]=res;
  94. 		}
  95. 		printf("%d\n",res);
  96. 	}
  97. 	return 0;
  98. }
  99.  
  100.  
  101.  
  102.  
Success #stdin #stdout 0s 7444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Uh7oXa
language:
C++ (gcc 8.3)
created:
9 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!