무방향 그래프 싸이클 확인

#include <iostream>
using namespace std;

int parent[10], n, m, num1, num2;

int getParent(int num)
{
    if(parent[num] == 0) return num;
    
    int ret = getParent(parent[num]);
    parent[num] = ret;
    
    return ret;
        
}
void uni(int num1, int num2)
{
    int n1 = getParent(num1);
    int m1 = getParent(num2);
    
    if(n1 > m1)
        parent[n1] = m1;
    else if(n1 < m1)
        parent[m1] = n1;
    else
    {
        cout << "싸이클 발생";
        return;
    }
}
int main()
{
 
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        cin >> num1 >> num2;
        uni(num1, num2);
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node{
    int cost, start, end;
};
int parent[100];
bool operator<(Node a, Node b)
{
    return a.cost > b.cost;
}
priority_queue<Node> q;

int getParent(int num)
{
    if(parent[num] == 0) return num;
    
    int ret = getParent(parent[num]);
    parent[num] = ret;
    
    return ret;
}
int uni(int num1, int num2)
{
    int n1 = getParent(num1);
    int m1 = getParent(num2);
    
    if(n1 > m1)
        parent[n1] = m1;
    else if(n1 < m1)
        parent[m1] = n1;
    else
        return -1;
    
    return 1;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        int begin, end, cost;
        cin >> begin >> end >> cost;
        q.push({cost, begin, end});
    }
    int cnt = 1, result = 0;
    while(cnt < n)
    {
        int num1 = q.top().start;
        int num2 = q.top().end;
        
        
        if(uni(num1, num2) == 1)
        {
            cnt++;
            result += q.top().cost;
        }
        
        
        q.pop();
    }
    cout << result;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    int n, m, start, end, table[100] = {0, }, used[100] = {0, };
    vector<int> sorting;
    priority_queue<int, vector<int>, greater<>> q;
    vector<pair<int, int>> path;
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        cin >> start  >> end;
        path.push_back({start, end});
        table[end]++;
    }
    while(sorting.size() < n)
    {
        for(int i=1; i<=n; i++)
        {
            if(used[i] == 1) continue;
            
            if(table[i] == 0 )
            {
                q.push(i);
                used[i] = 1;
            }
        }
        for(int i=0; i<path.size(); i++)
        {
            if(path[i].first == q.top())
                table[path[i].second]--;
        }
        sorting.push_back(q.top());
        q.pop();
    }
    for(int i=0; i<sorting.size(); i++)
        cout << sorting[i] << ' ';
    return 0;
}

// 위상 정렬
// 1. 0인 것을 찾아서 큐에 삽입
// 2. 큐에서 원소를 꺼내서 정렬 후, 시작하는 차수 -1
// 3. 차수가 0이면 큐에 삽입
// 4. 위의 1~3을 큐가 비어있을 때까지 반복
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, beg, en;
int table[100001];
vector<int> graph[100001];
vector<int> answer;
void topologysort()
{
    queue<int> q;
    for(int i=1; i<=n; i++)
    {
        if(table[i] == 0)
            q.push(i);
    }
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        answer.push_back(now);
        for(int i=0; i<graph[now].size(); i++)
        {
            table[graph[now][i]]--;
            if(table[graph[now][i]] == 0)
                q.push(graph[now][i]);
        }
    }
    
    for(int i=0; i<answer.size(); i++)
        cout << answer[i] << ' ';
}
int main()
{
   
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        cin >> beg >> en;
        graph[beg].push_back(en);
        table[en]++;
    }
    topologysort();
    return 0;
}

#include <iostream>
using namespace std;
int parent[100001];
int getParent(int num)
{
    if(parent[num] == num) return num;
    
    int ret = getParent(parent[num]);
    
    parent[num] = ret;
    
    return ret;
}
void uni(int type, int num1, int num2)
{
    int n1 = getParent(num1);
    int n2 = getParent(num2);
    if(type == 0)
    {
        if(n1 > n2)
            parent[n1] = n2;
        else
            parent[n2] = n1;
    }
    else
    {
        if(n1 == n2)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}
int main()
{
    int n, m, type, num1, num2;
    cin >> n >> m;
    for(int i=0; i<100001; i++)
        parent[i] = i;
    for(int i=0; i<m; i++)
    {
        cin >> type >> num1 >> num2;
        uni(type, num1, num2);
    }
    return 0;
}