uva - 10608 - Friends

這題我先把每個人的好友關係建成Adjacency-lists
之後再使用DFS search 來尋找全部的Connected component

再把成員數最多的Connected component印出來即可

不過這題用vector跟Adjacency-matrix來實做應該更方便

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm> 
using namespace std;

struct adj_node_struct         //用以紀錄每個人的好友關係
{
  int person_index;            //此人編號
  struct adj_node_struct *ptr;
};

struct person_index_struct      //紀錄每個人好友關係的根節點
{
  int value;                    //此人編號  
  struct adj_node_struct *ptr;
  int color;                    //此人是否被造訪過 0表未造訪  1表造訪中  2表造訪完畢
};

struct person_index_struct *person_index_struct_ptr;
int max_relation_count,test_relation_count;
void DFS_Visit(int i)  //使用DFS serach
{
  struct adj_node_struct *temp_adj_node_struct;
  if( (person_index_struct_ptr+i-1)->color != 2 )    //未造訪
  {
    if( (person_index_struct_ptr+i-1)->color == 0 )
    {
      test_relation_count++;
      (person_index_struct_ptr+i-1)->color = 1;   //開始造訪
    }
    else
      return;   //造訪中，跳過
    if( (person_index_struct_ptr+i-1)->ptr != NULL )   //開始造訪list元素
    {
      temp_adj_node_struct = (person_index_struct_ptr+i-1)->ptr;
      while(1)
      {
        DFS_Visit( temp_adj_node_struct->person_index );
        if( temp_adj_node_struct->ptr == NULL )
        {
          (person_index_struct_ptr+i-1)->color = 2;  //造訪結束
          break;
        }
        else
          temp_adj_node_struct = temp_adj_node_struct->ptr;  //繼續造訪下一個list元素
      }
    }
  }
}

int main()
{
  int test_case,person_num,relation_num;
  int index_a,index_b;
  int i;
  struct adj_node_struct *temp_adj_node_struct;
  cin>> test_case;  //幾組測資
  while(test_case--)
  {
    cin>> person_num;   //這組測資裡有幾個人
    cin>> relation_num; //這組測資裡有幾組朋友關係

    /**********初始化**********/
    person_index_struct_ptr = new struct person_index_struct[person_num];
    for(i=0;i<person_num;i++)
    {
      (person_index_struct_ptr+i)->value = i+1;
      (person_index_struct_ptr+i)->ptr = NULL;
      (person_index_struct_ptr+i)->color = 0;  
    }
    max_relation_count = 0;
    /********開始對adjacency list新增資料*********/
    while(relation_num--)
    {
      cin >> index_a;  //輸入好友關係
      cin >> index_b;

      /********對a儲存與好友b的關係**********/
      if( (person_index_struct_ptr+index_a-1)->ptr == NULL )
      {
        (person_index_struct_ptr+index_a-1)->ptr = new struct adj_node_struct;
        (person_index_struct_ptr+index_a-1)->ptr->person_index = index_b;
        (person_index_struct_ptr+index_a-1)->ptr->ptr = NULL;
      }
      else
      {
        temp_adj_node_struct = (person_index_struct_ptr+index_a-1)->ptr;
        while( (temp_adj_node_struct)->ptr != NULL )
        {
          temp_adj_node_struct = temp_adj_node_struct->ptr; 
        }
        temp_adj_node_struct->ptr = new struct adj_node_struct;
        temp_adj_node_struct->ptr->person_index = index_b;
        temp_adj_node_struct->ptr->ptr = NULL;
      }
      /********對b儲存與好友a的關係**********/
      if( (person_index_struct_ptr+index_b-1)->ptr == NULL )
      {
        (person_index_struct_ptr+index_b-1)->ptr = new struct adj_node_struct;
        (person_index_struct_ptr+index_b-1)->ptr->person_index = index_a;
        (person_index_struct_ptr+index_b-1)->ptr->ptr = NULL;
      }
      else
      {
        temp_adj_node_struct = (person_index_struct_ptr+index_b-1)->ptr;
        while( (temp_adj_node_struct)->ptr != NULL )
        {
          temp_adj_node_struct = temp_adj_node_struct->ptr; 
        }
        temp_adj_node_struct->ptr = new struct adj_node_struct;
        temp_adj_node_struct->ptr->person_index = index_a;
        temp_adj_node_struct->ptr->ptr = NULL;
      }
    }
    /***************開始DFS造訪****************/
    for(i=0;i<person_num;i++)
    {
      test_relation_count = 0;
      DFS_Visit( (person_index_struct_ptr+i)->value );  //傳入要造訪的人的編號
      if( test_relation_count > max_relation_count )
        max_relation_count = test_relation_count;
    }
    cout << max_relation_count << endl;
  }

  
  //system("pause");
    return 0;
}