Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.IO;
- namespace ConsoleApplication1
- {
- class Program
- {
- struct info
- {
- public int node,color;
- }
- static int N, M, Q;
- static List<info>[] tree;
- static string[] phrase = new string[3];
- static int[] phr = new int[3];
- static bool[,] visited;
- static public void read(int N)
- {
- phrase = Console.ReadLine().Split();
- for (int j = 0; j < N; ++j)
- {
- phr[j] = Convert.ToInt32(phrase[j]);
- }
- }
- static public int bfs(int st_node,int en_node)
- {
- Queue<info> que = new Queue<info>();
- info data = new info();
- int conNode,conColor;
- int cnt = 0;
- visited = new bool[N+1,M+1];
- que.Enqueue(new info { node = st_node, color = 0 });
- for (int i = 0; i <= N; ++i)
- for (int j = 0; j <= N; ++j)
- visited[i,j] = false;
- while (que.Count>0)
- {
- data = que.Dequeue();
- visited[data.node,data.color] = true;
- for (int i = 0; i < tree[data.node].Count; ++i)
- {
- conNode = tree[data.node][i].node;
- conColor = tree[data.node][i].color;
- if (data.color == 0 && !visited[conNode,conColor])
- {
- que.Enqueue(new info { node = conNode, color = conColor });
- if (conNode == en_node)
- ++cnt;
- }
- else if (data.color == tree[data.node][i].color && !visited[conNode, conColor])
- {
- que.Enqueue(new info { node = conNode, color = conColor });
- if (conNode == en_node)
- ++cnt;
- }
- }
- }
- return cnt;
- }
- static void Main(string[] args)
- {
- phrase = Console.ReadLine().Split();
- N = Convert.ToInt32(phrase[0]);
- M = Convert.ToInt32(phrase[1]);
- tree = new List<info>[N+1];
- for (int i = 0; i <= N; ++i)
- {
- tree[i] = new List<info>();
- }
- for (int i = 0; i < M; ++i)
- {
- read(3);
- tree[phr[0]].Add(new info { node = phr[1], color = phr[2] });
- tree[phr[1]].Add(new info { node = phr[0], color = phr[2] });
- }
- Q = Convert.ToInt32(Console.ReadLine());
- for (int i = 0; i < Q; ++i)
- {
- read(2);
- Console.WriteLine(bfs(phr[0], phr[1]));
- }
- // Console.ReadKey();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement