const int N_M = 1e6+2 ;
int N;
int dsu[N_M][6] ;
set <int> nodes ;
int degree[N_M] ;
int cnt4 = 0, cnt3 = 0 ;
int ans4 = 1, ans3 = 4 ;
vector <int> G[N_M] ;
int var[6] ;
int indi[N_M] ;
void Init(int N_) {
N = N_;
for ( int i = 0 ; i <= N ; ++i ) {
for ( int j = 0 ; j < 6 ; ++j ) dsu [i][j] = i, var[j] = 1 ;
}
}
int fnd ( int x, int d ) {
if ( x == dsu[x][d] ) return x ;
return dsu[x][d] = fnd ( dsu[x][d], d ) ;
}
int uni ( int x, int y, int d ) {
int fx = fnd(x, d) , fy = fnd(y, d) ;
if ( fx == fy ) return 0 ;
dsu[fx][d] = fy ;
return 1 ;
}
int yet = 1, nodeE ;
void Link(int A, int B) {
degree[A]++ ;
degree[B]++ ;
if ( degree[A] > 3 ) cnt4++, nodeE = A ;
if ( degree[B] > 3 ) cnt4++, nodeE = B ;
ans4 &= (cnt4 < 2) ;
G[A].push_back ( B ) ;
if ( cnt4 ) {
if ( yet ) {
for ( int i = 0 ; i <= N ; ++i ) {
if ( i == nodeE ) continue ;
for ( auto v:G[i] ) ans4 &= uni(i, v, 0) ;
}
}
ans4 &= uni(A,B,0) ;
yet = 0 ;
ans4 &= (nodes.count(nodeE)) ;
nodes.clear() ; nodes.insert (nodeE) ;
}
if ( degree[B] == 3 ) swap(A,B) ;
if ( degree[A] == 3 ) {
if ( cnt3 == 0 ) {
for ( auto v:G[A] ) nodes.insert (v) ;
nodes.insert(A) ;
int id = 1 ;
for ( auto j:nodes ) {
for ( int i = 0 ; i <= N ; ++i ) {
if ( i == j ) continue ;
for ( auto v:G[i] ) var[j] &= uni(i, v, id) ;
}
indi[j] = id ;
id++ ;
}
ans3 = nodes.size() ;
}
else {
set <int> cur ;
for ( auto v:G[A] ) if ( nodes.count(v) ) cur.insert (v) ;
if ( nodes.count(A) ) cur.insert (A) ;
nodes = cur ;
ans3 = nodes.size() ;
}
cnt3++ ;
}
if ( degree[B] == 3 ) {
set <int> cur ;
for ( auto v:G[B] ) if ( nodes.count(v) ) cur.insert (v) ;
if ( nodes.count(B) ) cur.insert (B) ;
nodes = cur ;
ans3 = nodes.size() ;
cnt3++ ;
}
if ( cnt3 ) {
set <int> cur ;
for ( auto v:nodes ) {
if ( v!=A && v!=B ) var[indi[v]] &= uni(A,B,indi[v]) ;
if ( var[indi[v]] ) cur.insert ( v ) ;
}
nodes = cur ;
ans3 = nodes.size() ;
}
if ( cnt4 ) ans4 &= (nodes.size()>0) ;
}
int CountCritical() {
if ( cnt4 ) return ans4 ;
if ( cnt3 ) return ans3 ;
return N;
}
Compilation message
rings.cpp:6:1: error: 'set' does not name a type
set <int> nodes ;
^~~
rings.cpp:10:1: error: 'vector' does not name a type
vector <int> G[N_M] ;
^~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:41:3: error: 'G' was not declared in this scope
G[A].push_back ( B ) ;
^
rings.cpp:51:16: error: 'nodes' was not declared in this scope
ans4 &= (nodes.count(nodeE)) ;
^~~~~
rings.cpp:51:16: note: suggested alternative: 'nodeE'
ans4 &= (nodes.count(nodeE)) ;
^~~~~
nodeE
rings.cpp:54:25: error: 'swap' was not declared in this scope
if ( degree[B] == 3 ) swap(A,B) ;
^~~~
rings.cpp:57:30: error: 'nodes' was not declared in this scope
for ( auto v:G[A] ) nodes.insert (v) ;
^~~~~
rings.cpp:57:30: note: suggested alternative: 'nodeE'
for ( auto v:G[A] ) nodes.insert (v) ;
^~~~~
nodeE
rings.cpp:58:10: error: 'nodes' was not declared in this scope
nodes.insert(A) ;
^~~~~
rings.cpp:58:10: note: suggested alternative: 'nodeE'
nodes.insert(A) ;
^~~~~
nodeE
rings.cpp:60:23: error: unable to deduce 'auto&&' from 'nodes'
for ( auto j:nodes ) {
^~~~~
rings.cpp:71:10: error: 'set' was not declared in this scope
set <int> cur ;
^~~
rings.cpp:71:10: note: suggested alternative: 'yet'
set <int> cur ;
^~~
yet
rings.cpp:71:15: error: expected primary-expression before 'int'
set <int> cur ;
^~~
rings.cpp:72:35: error: 'nodes' was not declared in this scope
for ( auto v:G[A] ) if ( nodes.count(v) ) cur.insert (v) ;
^~~~~
rings.cpp:72:35: note: suggested alternative: 'nodeE'
for ( auto v:G[A] ) if ( nodes.count(v) ) cur.insert (v) ;
^~~~~
nodeE
rings.cpp:72:52: error: 'cur' was not declared in this scope
for ( auto v:G[A] ) if ( nodes.count(v) ) cur.insert (v) ;
^~~
rings.cpp:73:15: error: 'nodes' was not declared in this scope
if ( nodes.count(A) ) cur.insert (A) ;
^~~~~
rings.cpp:73:15: note: suggested alternative: 'nodeE'
if ( nodes.count(A) ) cur.insert (A) ;
^~~~~
nodeE
rings.cpp:73:32: error: 'cur' was not declared in this scope
if ( nodes.count(A) ) cur.insert (A) ;
^~~
rings.cpp:74:10: error: 'nodes' was not declared in this scope
nodes = cur ;
^~~~~
rings.cpp:74:10: note: suggested alternative: 'nodeE'
nodes = cur ;
^~~~~
nodeE
rings.cpp:74:18: error: 'cur' was not declared in this scope
nodes = cur ;
^~~
rings.cpp:80:6: error: 'set' was not declared in this scope
set <int> cur ;
^~~
rings.cpp:80:6: note: suggested alternative: 'yet'
set <int> cur ;
^~~
yet
rings.cpp:80:11: error: expected primary-expression before 'int'
set <int> cur ;
^~~
rings.cpp:81:31: error: 'nodes' was not declared in this scope
for ( auto v:G[B] ) if ( nodes.count(v) ) cur.insert (v) ;
^~~~~
rings.cpp:81:31: note: suggested alternative: 'nodeE'
for ( auto v:G[B] ) if ( nodes.count(v) ) cur.insert (v) ;
^~~~~
nodeE
rings.cpp:81:48: error: 'cur' was not declared in this scope
for ( auto v:G[B] ) if ( nodes.count(v) ) cur.insert (v) ;
^~~
rings.cpp:82:11: error: 'nodes' was not declared in this scope
if ( nodes.count(B) ) cur.insert (B) ;
^~~~~
rings.cpp:82:11: note: suggested alternative: 'nodeE'
if ( nodes.count(B) ) cur.insert (B) ;
^~~~~
nodeE
rings.cpp:82:28: error: 'cur' was not declared in this scope
if ( nodes.count(B) ) cur.insert (B) ;
^~~
rings.cpp:83:6: error: 'nodes' was not declared in this scope
nodes = cur ;
^~~~~
rings.cpp:83:6: note: suggested alternative: 'nodeE'
nodes = cur ;
^~~~~
nodeE
rings.cpp:83:14: error: 'cur' was not declared in this scope
nodes = cur ;
^~~
rings.cpp:88:6: error: 'set' was not declared in this scope
set <int> cur ;
^~~
rings.cpp:88:6: note: suggested alternative: 'yet'
set <int> cur ;
^~~
yet
rings.cpp:88:11: error: expected primary-expression before 'int'
set <int> cur ;
^~~
rings.cpp:89:19: error: 'nodes' was not declared in this scope
for ( auto v:nodes ) {
^~~~~
rings.cpp:89:19: note: suggested alternative: 'nodeE'
for ( auto v:nodes ) {
^~~~~
nodeE
rings.cpp:91:30: error: 'cur' was not declared in this scope
if ( var[indi[v]] ) cur.insert ( v ) ;
^~~
rings.cpp:93:6: error: 'nodes' was not declared in this scope
nodes = cur ;
^~~~~
rings.cpp:93:6: note: suggested alternative: 'nodeE'
nodes = cur ;
^~~~~
nodeE
rings.cpp:93:14: error: 'cur' was not declared in this scope
nodes = cur ;
^~~
rings.cpp:96:24: error: 'nodes' was not declared in this scope
if ( cnt4 ) ans4 &= (nodes.size()>0) ;
^~~~~
rings.cpp:96:24: note: suggested alternative: 'nodeE'
if ( cnt4 ) ans4 &= (nodes.size()>0) ;
^~~~~
nodeE
