10473 | 2024-04-03 09:07:59 | UVince | Kritikus munkák | cpp17 | Hibás válasz 0/100 | 109ms | 46948 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) a.begin(),a.end()
const int MAXN=1e5+1;
vector<vector<int>> adj(MAXN);
vector<bool> vis(MAXN,false);
vector<int> tin(MAXN),low(MAXN);
int timer=0;
set<int> ans;
vector<pair<int,int>> fok(MAXN, {0,0});
void dfs(int v){
vis[v]=true;
for (int to:adj[v]){
if (!vis[to]) dfs(to);
}
}
void bridge(int v,int p=-1){
int cnt=0;
vis[v]=true;
tin[v]=low[v]=timer++;
for (int to : adj[v]){
if (to==p) continue;
if(vis[to]) low[v]=min(low[v], tin[to]);
else {
bridge(to,v);
low[v]=min(low[v],low[to]);
if(low[to]>=tin[v] && v!=1) ans.insert(v);
cnt++;
}
}
if (cnt>1 && v==1) ans.insert(1);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m;
cin>>n>>m;
for (int i = 0; i < m; i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
fok[u].first++;
fok[v].second++;
}
dfs(1);
for (int i=1;i<=n;i++){
if (!vis[i] && !adj[i].empty()){
cout<<"0\n";
}
}
vis.assign(MAXN,false);
bridge(1);
vector<int> be,ki;
for (int i=1;i<=n;i++){
if (fok[i].first==0) be.push_back(i);
if (fok[i].second==0) ki.push_back(i);
}
if (be.size()==1) ans.insert(be[0]);
if (ki.size()==1) ans.insert(ki[0]);
cout<<ans.size()<<"\n";
for (int i : ans) cout<<i<<" ";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 6ms | 9468 KiB | ||||
2 | Hibás válasz | 71ms | 18212 KiB | ||||
subtask2 | 0/25 | ||||||
3 | Hibás válasz | 4ms | 11568 KiB | ||||
4 | Hibás válasz | 6ms | 11716 KiB | ||||
5 | Hibás válasz | 6ms | 11812 KiB | ||||
6 | Elfogadva | 4ms | 11960 KiB | ||||
7 | Elfogadva | 7ms | 12788 KiB | ||||
subtask3 | 0/25 | ||||||
8 | Elfogadva | 20ms | 15536 KiB | ||||
9 | Hibás válasz | 10ms | 14100 KiB | ||||
10 | Hibás válasz | 12ms | 14492 KiB | ||||
11 | Hibás válasz | 16ms | 15404 KiB | ||||
12 | Hibás válasz | 16ms | 15208 KiB | ||||
subtask4 | 0/25 | ||||||
13 | Hibás válasz | 57ms | 26628 KiB | ||||
14 | Hibás válasz | 52ms | 22152 KiB | ||||
15 | Elfogadva | 54ms | 26708 KiB | ||||
16 | Elfogadva | 50ms | 26028 KiB | ||||
17 | Hibás válasz | 50ms | 26680 KiB | ||||
subtask5 | 0/25 | ||||||
18 | Hibás válasz | 104ms | 34092 KiB | ||||
19 | Hibás válasz | 109ms | 36864 KiB | ||||
20 | Hibás válasz | 104ms | 41144 KiB | ||||
21 | Hibás válasz | 101ms | 42444 KiB | ||||
22 | Hibás válasz | 104ms | 46948 KiB |