https://oj.luyencode.net/problem/NYTRAVEL

[utterances-bot]

Mạng lưới giao thông - Luyện Code Online

https://oj.luyencode.net/problem/NYTRAVEL

[bibimoni]

View code AC

\``` // https://oj.luyencode.net/problem/NYTRAVEL #include using namespace std; using ll = long long; int n, m; const int maxN = 100001; vector adj[maxN]; bool visited[maxN]; int v = 0; void BFS(int src) { visited[src] = true; queue Q; Q.push(src); v++; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (auto it : adj[u]) { if (!visited[it]) { visited[it] = true; Q.push(it); v++; } } } } void input() { cin >> n >> m; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); visited[i] = false; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); input(); memset(visited, false ,sizeof(visited)); int maxC = 0; int res = 0; BFS(1); // the team is currently at city number 1 so we get its vertexes first res = v; v = 0; for(int i = 2; i <= n; i++) { if (!visited[i]) { BFS(i); maxC = max(v, maxC); v = 0; } } cout << res + maxC; return 0; } \```

[DangLun]

AC

Xem code AC

#include #define ll long long #define pb push_back using namespace std; const int maxn = 100001; vector adj[maxn]; int visited[maxn]; int ck[maxn]; int cnt = 0; void bfs(int u){ queue q; visited[u] = true; q.push(u); while(!q.empty()){ int v = q.front(); q.pop(); ck[cnt]++; for(auto x: adj[v]){ if(!visited[x]){ q.push(x); visited[x] = true; } } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; memset(visited, false, sizeof(visited)); for(int i = 0; i < m; i++){ int x, y; cin >> x >> y; adj[x].pb(y); adj[y].pb(x); } for(int i = 1; i<= n; i++){ if(!visited[i]){ ++cnt; bfs(i); } } int max = 0; for(int i = 2; i<= cnt; i++){ if(ck[i] > max){ max = ck[i]; } } cout << ck[1] + max; }