DFS color count
DFS题，但是犯了很多错误，http://codeforces.com/contest/505/problem/B
里面的图是多重边，每条边有color，保证两个点之间的边不会重色，也就是加一重循环，但是犯了很多错误，一直WA
对于输入点构建图忘记加上对立边了，例如mat[a][b]=c, mat[b][a]=c, 之前也翻过类似错误
对于dfs还是不熟练，炒肉大神建议局部变量传递，返回值设计，参数设计。关键是找到递归结构，结果找递归结构的时候已经看错题了。
看成路径的个数，而不是color的种类数。int dfs, dfs(s,e)=sum(i:1->n &&
3.DFS框架是先判是否递归出口，也即找到目的点，如果不到终点，则判断是否已经访问过，当然也可以放在for循环里，但是这样结构清楚，
除非是必须比较当前与下一层的一个属性，然后又不加参数这样。这两个出口有时候可以互换，有时又不行，例如之前lc的一道word search，
自己第一遍写的时候老是死循环，后来G神帮我调代码就发现了问题，先判是否word到头了，再判是否访问过了。
由于需要判断当前颜色是否始终一致，如果从起点调用一次dfs，那么第一层的时候颜色是不需要判断的，因此还要设置变量来判断，这样很麻烦，
于是for循环调用dfs，但是忘记设置v[s]=1visit 数组初始化位置不正确，放在每一个query开始
如果是需要遍历整个图的，需要再出口之后v[cur]=1, 同时最后return之前v[cur]=0, 这是中间没有return的情况，如果有的话，必须先v[cur]=0 复原，
然后return ，否则有些状态变了返回到上一层的时候不能复原导致出错。用一个color数组来存是否 计算过且有路径，有的话置为1, 本质和hash一样。
代码如下：
#include<set>
#include<map>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<cstdio>
#include<string>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<fstream>
#include<iostream>
#include<algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
const int maxn = 1e2 + 10;
typedef long long LL;
typedef unsigned long long ULL;
//int, -2^31~2^31-1 -2.1*10^9~2.1*10^9 (-2147483648-2147483647)
//unsigned int, 0~2^32-1 0~4.2*10^9
//long long -2^63~2^63-1 -9*10^18~9*10^18
//unsigned long long 0~2^64-1 0~1.8*10^19
bool v[maxn];
bool validcolor[maxn];
int n;
vector<int> mat[maxn][maxn];
int dfs(int cur, int e, int color)
{
if(cur==e) return 1;
if(v[cur]) return 0;
v[cur]=1;
int sum=0;
for(int i=1;i<=n;i++)
{
if(i==cur) continue;
for(auto ele: mat[cur][i])
if(ele==color && dfs(i, e, color)) {v[cur]=0; return 1;}
}
v[cur]=0;
return 0;
}
int main()
{
/*
#ifndef ONLINE_JUDGE
freopen ("in.txt" , "r" , stdin);
freopen ("out.txt" , "w" , stdout);
#endif
*/
int m, q, qu, qv, x,y, c;
for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) mat[i][j].clear();
cin>>n>>m;
for(int i=0;i<m;i++) cin>>x>>y>>c, mat[x][y].push_back(c), mat[y][x].push_back(c);
cin>>q;
for(int i=0;i<q;i++)
{
cin>>qu>>qv;
memset(validcolor, 0, sizeof validcolor);
for(int i=1;i<=n;i++)
{
memset(v, 0 ,sizeof v);
if(i==qu) continue;
v[qu]=1;
for(auto ele: mat[qu][i])
if(!validcolor[ele] && dfs(i, qv, ele)) validcolor[ele]=1;;
}
int sum=0;for(int j=1;j<=m;j++) sum+=validcolor[j];
cout<<sum<<endl;
}
return 0;
}