24.01.02 12:38 작성
·
177
0
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define endl "\n"
void merge(int a, int b);
int find(int a);
vector<int> parent;
vector<int> paths;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n;
cin >> m;
parent.resize(n + 1);
for (int i = 0; i <= n; ++i)
{
parent[i] = i;
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
int v;
cin >> v;
if (v == 1)
{
merge(i, j);
}
}
}
for (int i = 1; i <= n; ++i)
{
int n;
cin >> n;
paths.push_back(n);
}
int prevPath = find(paths[0]);
for (int path : paths)
{
int curPath = find(path);
if (curPath != prevPath)
{
cout << "NO";
return 0;
}
prevPath = curPath;
}
cout << "YES";
return 0;
}
void merge(int a, int b)
{
a = find(a);
b = find(b);
if (a != b)
parent[b] = a;
}
int find(int a)
{
if (a == parent[a])
return a;
return parent[a] = find(parent[a]);
}
왜맞틀인거같은 느낌이 듭니다.
책에 있는 내용 분석해서 이해는 하였는데 제가 짠 코드가 왜 틀린것인지 모르겠습니다.
의심되는 부분은 처음에 merge하는 for문인거같은데
책처럼 인접리스트를 사용하지 않고 v가 1이라면(i행과 j열이 연결되어 있다면) 그냥 바로 merge하여 병합하였는데 이부분에 예외가 있는것인지 아니면 다른 부분에서 예외가 있는것인지 감이 안 잡히는데 어디가 잘 못된것인지 한번 봐주실 수 있나요?
감사합니다 :)
답변 1
0
2024. 01. 03. 00:37
안녕하세요. 반갑습니다.
아마도 Path를 저장하는 반복문에 약간 로직이 잘못된 것으로 보입니다.
해당 부분을
for (int i = 1; i <= n; ++i) {
int n;
cin >> n;
paths.push_back(n);
}
아래와 같이 수정하시면 되지 않을까 싶습니다.
for (int i = 1; i <= m; i++)
{
int path;
cin >> path;
paths.push_back(path);
}
감사합니다.
새해 복 많이 받으세요 :)