題解【Codeforces 1184 E 1】Daleks'Invasion(easy)

問題面
まず最初のエッジを考慮せずにKruskal最小生成ツリーを1回走ります.
各エッジについて、接続された2つの連通成分が第1のエッジの両端点の連通成分である場合、答えはこのエッジの重みです.
このエッジが見つからない場合は、このエッジが図のエッジであることを示し、直接(10^9)を出力します.

#include 

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

const int INF = 0x3f3f3f3f, N = 100003, M = 1000001;

int n, m;
int fa[N];
struct Node
{
	int u, v, w;
} a[M];

inline bool cmp(Node x, Node y)
{
	return x.w < y.w;
}

int getf(int u) 
{
	if (fa[u] == u) return u;
	return fa[u] = getf(fa[u]);
}

int main()
{
    n = gi(), m = gi();
    for (int i = 1; i <= m; i+=1)
    	a[i].u = gi(), a[i].v = gi(), a[i].w = gi();
    for (int i = 1; i <= n; i+=1) fa[i] = i;
    sort(a + 2, a + 1 + m, cmp);
    bool fl = true;
    for (int i = 2; i <= m; i+=1)
    {
    	int u = getf(a[i].u), v = getf(a[i].v);
    	if (u != v)
    	{
    		int x = getf(a[1].u), y = getf(a[1].v);
    		if ((x == u && y == v) || (x == v && y == u))
    		{
    			printf("%d
", a[i].w);
    			fl = false;
    			break;
    		}
    		fa[u] = v;
    	}
    }
    if (fl) puts("1000000000");
    return 0;
}