[백준] 1762 - 평면그래프와 삼각형 (c++)

https://www.acmicpc.net/problem/1762

 

문제 요약

평면 그래프가 주어진다. 크기가 3인 사이클의 개수를 구해라.

 

풀이 (M)

• 그리디

평면 그래프라는게 중요하다. 완전 그래프 처럼 정점마다 간선이 많이 붙어 있는 형태면 시간초과를 피할 수가 없다. 하지만 평면 그래프는 이런 형태가 나올 수 없다. 간선이 많이 붙어있는 한 정점을 여러 번 방문하지 않도록 처리해주면 해결할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    vector<unordered_set<int>> adj(n+1);
    vector<array<int,2>> ed;
    for(int i=0,u,v;i<m;i++)
        cin>>u>>v,adj[u].insert(v),adj[v].insert(u),ed.push_back({u,v});

    ll ans=0;
    for(auto&[u,v]:ed) {
        if(adj[u].size()>adj[v].size())
            swap(u,v);
        for(auto&x:adj[u])
            if(adj[v].contains(x))
                ans++;
    }   
    cout<<ans/3;
}