题目链接:
题目大意:
给出一个有向图,边有不同的颜色,任意给出查询,查询两点能够只通过一种颜色连通的颜色的种类数。
题目分析:
根据不同颜色建边,bfs即可,队列维护可用的点。
AC代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 107
using namespace std;
int n,m,c,x,y,q;
vector<int> e[MAX][MAX];
bool vis[MAX];
void add ( int u , int v , int w )
{
e[w][u].push_back ( v );
e[w][v].push_back ( u );
}
bool bfs ( int c )
{
memset ( vis , 0 , sizeof ( vis ) );
queue<int> q;
q.push ( x );
while ( !q.empty() )
{
int u = q.front();
if ( u == y ) return true;
q.pop();
for ( int i = 0 ; i < e[c][u].size() ; i++ )
{
int v = e[c][u][i];
if ( vis[v] ) continue;
vis[v] = true;
q.push ( v );
}
}
return false;
}
int main ( )
{
while ( ~scanf ( "%d%d" , &n , &m ) )
{
for ( int i = 0 ; i < MAX ; i++ )
for ( int j = 0 ; j < MAX ; j++ )
e[i][j].clear();
for ( int i = 0 ; i < m ; i++ )
{
scanf ( "%d%d%d" , &x , &y , &c );
add ( x , y , c );
}
scanf ( "%d" , &q );
while ( q-- )
{
int ans = 0;
scanf ( "%d%d" , &x , &y );
for ( int i = 1 ; i <= m ; i++ )
if ( bfs ( i ) ) ans++;
printf ( "%d\n" , ans );
}
}
}