Advertisement
Guest User

Untitled

a guest
Jan 21st, 2015
645
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.05 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.IO;
  6.  
  7.  
  8. namespace ConsoleApplication1
  9. {
  10.     class Program
  11.     {
  12.         struct info
  13.         {
  14.             public int node,color;
  15.         }
  16.  
  17.         static int N, M, Q;
  18.         static List<info>[] tree;
  19.         static string[] phrase = new string[3];
  20.         static int[] phr = new int[3];
  21.         static bool[,] visited;
  22.  
  23.  
  24.         static public void read(int N)
  25.         {
  26.             phrase = Console.ReadLine().Split();
  27.             for (int j = 0; j < N; ++j)
  28.             {
  29.                 phr[j] = Convert.ToInt32(phrase[j]);
  30.             }
  31.         }
  32.  
  33.  
  34.         static public int bfs(int st_node,int en_node)
  35.         {
  36.             Queue<info> que = new Queue<info>();
  37.             info data = new info();
  38.             int conNode,conColor;
  39.             int cnt = 0;
  40.             visited = new bool[N+1,M+1];
  41.            
  42.  
  43.             que.Enqueue(new info { node = st_node, color = 0 });
  44.            
  45.             for (int i = 0; i <= N; ++i)
  46.                 for (int j = 0; j <= N; ++j)
  47.                     visited[i,j] = false;
  48.  
  49.  
  50.             while (que.Count>0)
  51.             {
  52.                 data = que.Dequeue();
  53.                 visited[data.node,data.color] = true;
  54.  
  55.                 for (int i = 0; i < tree[data.node].Count; ++i)
  56.                 {
  57.                     conNode = tree[data.node][i].node;
  58.                     conColor = tree[data.node][i].color;
  59.  
  60.                     if (data.color == 0 && !visited[conNode,conColor])
  61.                     {
  62.                         que.Enqueue(new info { node = conNode, color = conColor });
  63.  
  64.                         if (conNode == en_node)
  65.                             ++cnt;
  66.                     }
  67.  
  68.                     else if (data.color == tree[data.node][i].color && !visited[conNode, conColor])
  69.                     {
  70.                         que.Enqueue(new info { node = conNode, color = conColor });
  71.  
  72.                         if (conNode == en_node)
  73.                             ++cnt;
  74.                     }      
  75.                 }
  76.             }
  77.  
  78.  
  79.             return cnt;
  80.         }
  81.  
  82.        
  83.  
  84.         static void Main(string[] args)
  85.         {
  86.             phrase = Console.ReadLine().Split();
  87.             N = Convert.ToInt32(phrase[0]);
  88.             M = Convert.ToInt32(phrase[1]);
  89.  
  90.             tree = new List<info>[N+1];
  91.             for (int i = 0; i <= N; ++i)
  92.             {
  93.                 tree[i] = new List<info>();
  94.             }
  95.  
  96.             for (int i = 0; i < M; ++i)
  97.             {
  98.                 read(3);
  99.  
  100.                 tree[phr[0]].Add(new info { node = phr[1], color = phr[2] });
  101.                 tree[phr[1]].Add(new info { node = phr[0], color = phr[2] });
  102.             }
  103.  
  104.             Q = Convert.ToInt32(Console.ReadLine());
  105.             for (int i = 0; i < Q; ++i)
  106.             {
  107.                 read(2);
  108.                 Console.WriteLine(bfs(phr[0], phr[1]));
  109.             }
  110.  
  111.            // Console.ReadKey();
  112.         }
  113.  
  114.                
  115.     }
  116.  
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement