| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1362755 | kokoroo | Social Engineering (EGOI22_socialengineering) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
#define rep(i,n) for(ll i=0; i<n; i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define print(a) cout<<a<<endl
typedef long long ll;
#define yn(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YN(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define so(a) sort(a.begin(),a.end())
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vs vector<string>
#define pb push_back
#define a2i(a,s) (ll)(a-s)
#define i2a(s,a) (char)(s+a)
#define ssize(a) a.size()
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<pair<ll,ll>,ll> P3;
typedef pair<pair<ll,ll>,pair<ll,ll>> P4;
typedef pair<ll, ll> Pll;
typedef pair<ll,Pll> Plll;
typedef pair<Pii, int> Piii;
const ll INF = 1000000000000000000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
class UnionFind{
public:
ll par[100009];//親
ll siz[100009];//クラブ
//ｎ頂点のグラフ
void init(ll n){
for(ll i=1;i<=n;i++)par[i]=-1;
for(ll i=1;i<=n;i++)siz[i]=1;
}
//根
ll root(ll x){
while(true){
if(par[x]==-1)break;
x=par[x];
}
return x;
}
//統合
void unite(ll x,ll y){
ll X=root(x);
ll Y=root(y);
if(X==Y)return;
if(siz[X]<siz[Y]){
par[X]=Y;
siz[Y]=siz[Y]+siz[X];
}
else{
par[Y]=X;
siz[X]=siz[Y]+siz[X];
}
}
//連結かどうか
bool same(ll x,ll y){
if(root(x)==root(y))return true;
else return false;
}
//サイズ
ll sizee(ll x){
return siz[root(x)];
}
};
UnionFind uf;
void MakeMove(int v){
if(v==1)GetMove();
else{
for(int nx:g[v]){
if(nx!=v){
MakeMove(nx);
break;
}
}
}
}
void SocialEngineering(int n, int m, vector<pair<int,int>> edges){
//辺を作る
vector<int> g[n+1];
for(ll i=0;i<m;i++){
int a=edges[i].first,b=edges[i].second;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> visited(n+1);
bool b=true;
visited[1]=1;
for(ll i=0;i<g[1].size();i++){
if(visited[g[1][i]]==0){
queue<Pll> que;
que.push({1,i});
while(!que.empty()){
Pll p=que.front();
que.pop();
ll re=p.first;
ll pos=p.second;
visited[pos]=1;
for(auto nx:g[pos]){
if(nx!=re&&visited[nx]>0){
b=false;
break;
}
que.push({pos,nx});
}
}
}
}
if(b==false)return;
GetMove();
}
// int main(){
// //入力
// cin.tie(0);
// ios::sync_with_stdio(0);
// return 0;
// }