글 읽기 - 질문 게시판에 있는 반례를 거의다 해본것 같은데 못찾겠습니다.

dufdif 5년 전 0

음 문제를 유니온 파인드로 푸는중입니다.

근데 도저히 반례를 못찾겠어서 올립니다..

#include<vector>
#include<algorithm>
#include<iostream>
#include<stack>
#include<queue>
#include<set>

#include<functional>
using namespace std;

struct Edge
{
 int nextid;
 float weight;
 Edge() : nextid(0), weight(0) {}
 Edge(int i, float w) : nextid(i), weight(w) {}
 
};

bool operator<(const Edge& a,const Edge& b)
{
 return a.nextid < b.nextid;
}


struct Node
{
 int id;//버텍스(노드) 고유 아이디
 int rootid; // 이 노드의 루트노드의 id

 set<Edge> edges;//연결된 간선들. 셋으로 하는이유는 추후 해당 연결된 노드가 있는지 찾을때 속도적으로 이익을 보기 위해서.
 


 Node() = default;
 Node(int _id, int _rootid) : id(_id), rootid(_rootid) { }


 
 


};


//MST 용 데이터. 무방향 버텍스 아이디 2개를 저장하고, 가중치를 가진다.
struct MSTEdge
{
 int id1;
 int id2;
 int weight;
 MSTEdge(int i1, int i2, int w) : id1(i1), id2(i2), weight(w) {}
};



//정렬시 키는 내림차순이며, 
bool operator<(const MSTEdge& a, const MSTEdge& b)
{
 return a.weight < b.weight;//키의 비교는 weight가 작을수록 우선순위가 높은 키이다.
}


//무방향 전용 . BFS 와 MST, 정점 추가/제거 , 간선 추가/제거
class UndirectGraph
{
private:
 vector<Node> vertexs;
public:
 Node GetVertex(int id) { return vertexs[id - 1]; }
 int GetVertexSize() { return vertexs.size(); }
 multiset<MSTEdge> mstedges;//MST만들때 사용되는 데이터들. 멀티셋인 이유는 가중치를 기준으로 정렬하는데, 가중치가 같은경우가 있을 수 있으니까.
 UndirectGraph() { vertexs.reserve(30); }
 void Push_Vertex() 
 {
  vertexs.push_back(Node(vertexs.size() + 1, vertexs.size() + 1)); 
  
 
 }
 void Del_Vertex(int _id)
 {
  auto it=vertexs.begin(); // 시작위치 얻어옴.
  vertexs.erase(it + _id - 1);//id는 1부터 시작이고 인덱스는 0부터 시작이므로 1을 빼준다.
  
 }


 void Edge_Link(int start, int end, int w=1)
 {
  vertexs.at(start - 1).edges.insert(Edge(end, w));
  vertexs.at(end - 1).edges.insert(Edge(start, w)); 
  mstedges.insert(MSTEdge(start, end, w));
 }
 void Edge_UnLink(int start, int end, int w = 1)
 {
  if (vertexs.at(start - 1).isLinkNode(Edge(end - 1, w)) == true && vertexs.at(end - 1).isLinkNode(Edge(start - 1, w)) == true)
  {
   vertexs.at(start - 1).edges.erase(Edge(end - 1, w));
   vertexs.at(end - 1).edges.erase(Edge(start - 1, w));
   mstedges.erase(MSTEdge(start, end, w));
  }
 }

​​


 //유니온 - 파인드 에서 합병 . 만약 결과가 false면 같은 소속인것.
 bool UnionMerge(int start, int end) 
 {
  //먼저 두개의 정점 아이디가 속한 루트를 찾음.
  int id1 = UnionFind(start);
  int id2 = UnionFind(end);


  if (id1 == id2)
   return false;


  
  //소속이 다르면 end의 루트를 start로 삼는다.
  vertexs[end - 1].rootid = vertexs[start - 1].rootid;

  return true;
 }
 //유니온 - 파인드 에서 자기가 속한 루트를 반환
 int UnionFind(int id)
 {
  //루트 아이디가 곧 자신이면 반환.
  if (id == vertexs[id - 1].rootid)
   return id;


  //아니라면 루트아이디를 찾고 갱신한다.
  return vertexs[id - 1].rootid = UnionFind(vertexs[id - 1].rootid);
 }


 
  }


  return mst;
 }


};



int main()
{
 UndirectGraph ug;
 int n;
 int m;


 cin >> n;
 cin >> m;


 for (int i = 0; i < n; i++)
  ug.Push_Vertex();


 for (int i = 0; i < m; i++)
 {
  int s, e;
  cin >> s >> e;


  ug.Edge_Link(s, e);
 }
 int maxheight = 0;
 for (auto i =ug.mstedges.begin(); i != ug.mstedges.end(); i++)
 {
  ug.UnionMerge(i->id1, i->id2);
 }


 int count = 0;
 for (int i = 2; i <= ug.GetVertexSize(); i++)
 {
  if (ug.UnionFind(1) == ug.UnionFind(i))
   count += 1;
  
 }
 cout << count << endl;


    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문 게시판에 있는 반례를 거의다 해본것 같은데 못찾겠습니다.

dufdif 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말