"NOIP simulation" looking for triangles [three-element ring]

题描述

In the undirected graph, if there are edges between three different vertices, they are said to form a triangle.   In an undirected graph G, there is one and only one triangle. Now your task is to find it.

Input format

The first line of the number n, mn, m, represents the number of vertices of G and the number of sides.   Next mm lines, two numbers per line i, ji, j means that there is an edge between points ii and jj. The title guarantees no heavy edges and self-loops.

output format

output one line, three integers, i < j < ki

#include <set>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

const int N=1e5+5;

int ans[4];
int n,m,s,vis[N],out[N],link[N];

set<int>st;
vector<int>G[N];

inline int read() {
    int x=0;char ch=getchar();bool f=0;
    while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?-x:x;
}

int main() {
    n=read(),m=read();s=sqrt(m);

    for(int i=1;i<=m;i++) {
        int x=read(),y=read();
        out[x]++,out[y]++;
        G[x].push_back(y);
        G[y].push_back(x);

        st.insert((ll)x*n+y);
        st.insert((ll)y*n+x);
    }

    for(int i=1;i<=n;i++) {
        int x=i;vis[x]=1;
        for(int j=0;j<G[x].size();j++) link[G[x][j]]=x;
        for(int j=0;j<G[x].size();j++) {
            int y=G[x][j];
            if(vis[y]) continue;

            if(out[y]<=s) {
                for(int k=0;k<G[y].size();k++) {
                    int z=G[y][k];
                    if(link[z]==x) {
                        ans[1]=x,ans[2]=y,ans[3]=z;
                        sort(ans+1,ans+1+3);
                        printf("%d %d %d",ans[1],ans[2],ans[3]);return 0;
                    }
                }
            } else {
                for(int k=0;k<G[x].size();k++) {
                    int z=G[x][k];
                    if(st.find((ll)z*n+y)!=st.end()) {
                        ans[1]=x,ans[2]=y,ans[3]=z;
                        sort(ans+1,ans+1+3);
                        printf("%d %d %d",ans[1],ans[2],ans[3]);return 0;
                    }
                }
            }
        }
    }

    return 0;
}