分享|dds
26
发布于 江西

import java.io.*;

import java.util.*;

public class Main {

// 使用快速IO,应对 10^6 级别数据

static class FastReader {

BufferedReader br;

StringTokenizer st;

public FastReader() {

br = new BufferedReader(new InputStreamReader(System.in));

}

String next() {

while (st == null || !st.hasMoreElements()) {

try {

String line = br.readLine();

if (line == null) return null;

st = new StringTokenizer(line);

} catch (IOException e) {

e.printStackTrace();

}

}

return st.nextToken();

}

int nextInt() {

return Integer.parseInt(next());

}

}

public static void main(String[] args) {

FastReader in = new FastReader();

PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

String nStr = in.next();

if (nStr == null) {

out.close();

return;

}

int n = Integer.parseInt(nStr);

int m = in.nextInt();

int k = in.nextInt();

// 使用数组模拟邻接表(链式前向星),节省内存

int[] head = new int[n + 1];

Arrays.fill(head, -1);

int[] to = new int[2 * m];

int[] next = new int[2 * m];

int edgeCount = 0;

for (int i = 0; i < m; i++) {

int u = in.nextInt();

int v = in.nextInt();

int w = in.nextInt();

// 只加入距离 <= k 的合法边

if (w <= k) {

to[edgeCount] = v;

next[edgeCount] = head[u];

head[u] = edgeCount++;

to[edgeCount] = u;

next[edgeCount] = head[v];

head[v] = edgeCount++;

}

}

List<Integer> ans = new ArrayList<>();

// 统计每个节点在合法子图中的度数

for (int i = 1; i <= n; i++) {

int degree = 0;

for (int e = head[i]; e != -1; e = next[e]) {

degree++;

}

// 度数为 0 或 1 的节点就是可能的终止位置

if (degree <= 1) {

ans.add(i);

}

}

// 输出结果

out.println(ans.size());

for (int i = 0; i < ans.size(); i++) {

out.print(ans.get(i));

if (i != ans.size() - 1) {

out.print(" ");

}

}

out.println(); // 打印换行

out.flush();

out.close();

}

}

评论 (0)