值得借鉴的代码
数据结构板子
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdint>
#include <cstddef>
#include <cmath>
#include <cstring>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <chrono>
#include <functional>
#include <numeric>
#include <utility>
#include <array>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
namespace dutinmeow {
namespace types {
using int8 = int_fast8_t;
using int16 = int_fast16_t;
using int32 = int_fast32_t;
using int64 = int_fast64_t;
using ll = int_fast64_t;
#define int int32
using uint8 = uint_fast8_t;
using uint16 = uint_fast16_t;
using uint32 = uint_fast32_t;
using uint64 = uint_fast64_t;
using ull = uint_fast64_t;
using pii = pair<int, int>;
using piii = pair<int, pii>;
using pll = pair<ll, ll>;
using plll = pair<ll, pll>;
template<class K, class V>
using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
template<class K>
using ordered_set = ordered_map<K, null_type>;
}
using namespace types;
namespace constants {
const int inf = 2000000011;
const ll llinf = 999999999999999989;
const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};
}
using namespace constants;
namespace macros {
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define EB emplace_back
#define EF emplace_front
#define MP make_pair
#define FF first
#define SS second
}
using namespace macros;
namespace hash {
struct chash {
const uint64_t C = ll(2e18 * PI) + 71;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
inline ll operator()(ll x) const { return __builtin_bswap64((x ^ RANDOM) * C); }
inline ll operator()(pll p) const { return (*this)(p.FF) ^ (*this)(p.SS); }
};
template<class K, class V>
using fast_map = gp_hash_table<K, V, chash>;
template<class K>
using fast_set = fast_map<K, null_type>;
}
using namespace hash;
namespace functions {
inline void stop() { assert(0); }
template<typename T>
inline void sort(T& c) { sort(c.begin(), c.end()); }
template<typename T, typename S>
inline void sort(T& c, S s) { sort(c.begin(), c.end(), s); }
template<typename T>
inline void reverse(T& c) { reverse(c.begin(), c.end()); }
// lambda template: [](const C& a, const C& b) { return a > b; }
inline ll ceil0(ll a, ll b) {
return a / b + ((a ^ b) > 0 && a % b);
}
inline ll floor0(ll a, ll b) {
return a / b - ((a ^ b) < 0 && a % b);
}
ll pow0(ll a, ll b) {
ll res = 1;
for (a %= MOD; b; b >>= 1) {
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
}
return res;
}
template<typename T>
string binary(T b) {
string res = "";
for (int i = sizeof(T) * 8 - 1; i >= 0; i--)
res += (b & (1 << i) ? '1' : '0');
return res;
}
template<typename T>
string binary(T b, int k) {
string res = "";
for (int i = k; i >= 0; i--)
res += ((b & (1 << i)) ? '1' : '0');
return res;
}
}
using namespace functions;
namespace input {
void filein(const string FILENAME) { freopen(FILENAME.c_str(), "r", stdin); }
inline void read() {}
template<typename T, typename... U>
inline void read(T& F, U&... S) {
cin >> F;
read(S...);
}
// pair
template<typename T1, typename T2>
inline istream& operator>>(istream& is, pair<T1, T2>& p) {
return is >> p.FF >> p.SS;
}
// std::array<T, N>
template<typename T, size_t sz>
inline istream& operator>>(istream& is, array<T, sz>& a) {
for (auto& x : a)
is >> x;
return is;
}
template<typename T, size_t sz>
void read(array<T, sz>& a, int n) {
assert(0 <= n && n < a.size());
for (int i = 0; i < n; i++)
cin >> a[i];
}
template<typename T, size_t sz>
void read(array<T, sz>& a, int l, int r) {
assert(0 <= l && l <= r && r < a.size());
for (int i = l; i <= r; i++)
cin >> a[i];
}
// std::vector<T>
template<typename T>
inline istream& operator>>(istream& is, vector<T>& v) {
for (auto& x : v)
is >> x;
return is;
}
template<typename T>
void read(vector<T>& v, int n) {
assert(0 <= n && n < v.size());
for (int i = 0; i < n; i++)
cin >> v[i];
}
template<typename T>
void read(vector<T>& v, int l, int r) {
assert(0 <= l && l <= r && r < v.size());
for (int i = l; i <= r; i++)
cin >> v[i];
}
}
using namespace input;
namespace output {
void fileout(const string FILENAME) { freopen(FILENAME.c_str(), "w", stdout); }
void fileerr(const string FILENAME) { freopen(FILENAME.c_str(), "w", stderr); }
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
return os << '(' << p.FF << ", " << p.SS << ')';
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << '[';
if (v.size()) {
os << *v.begin();
for (auto i = ++v.begin(); i != v.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream& operator<<(ostream& os, const ordered_set<T>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream& operator<<(ostream& os, const fast_set<T>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream& operator<<(ostream& os, const multiset<T>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const ordered_map<T1, T2>& s) {
os << '[';
if (s.size()) {
os << '(' << s.begin()->FF << " : " << s.begin()->SS << ')';
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << '(' << i->FF << " : " << i->SS << ')';
}
return os << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const fast_map<T1, T2>& s) {
os << '[';
if (s.size()) {
os << '(' << s.begin()->FF << " : " << s.begin()->SS << ')';
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << '(' << i->FF << " : " << i->SS << ')';
}
return os << ']';
}
#define fixfloat(d) fixed << setprecision(d)
void print() {}
template<typename T, typename... U>
void print(T F, U... S) {
cout << F;
print(S...);
}
void printl() {}
template<typename T, typename... U>
void printl(T F, U... S) {
cout << F << '\n';
printl(S...);
}
template<typename T>
void prints(T F) {
cout << F;
}
template<typename T, typename... U>
void prints(T F, U... S) {
cout << F << ' ';
prints(S...);
}
void printc(string c) {}
template<typename T, typename... U>
void printc(const string c, T F, U... S) {
cout << F << c;
printc(c, S...);
}
void println() { cout << '\n'; }
template<typename T, typename... U>
void println(T F, U... S) {
cout << F << ' ';
println(S...);
}
template<typename T, size_t sz>
void print(array<T, sz>& a, string s = " ", string e = "\n") {
for (int i = 0; i < a.size(); i++)
print(a[i], s);
print(e);
}
template<typename T, size_t sz>
void print(array<T, sz> a, int n, string s = " ", string e = "\n") {
assert(0 <= n && n <= a.size());
for (int i = 0; i < n; i++)
print(a[i], s);
print(e);
}
template<typename T, size_t sz>
void print(array<T, sz> a, int l, int r, string s = " ", string e = "\n") {
assert(0 <= l && l < r && r < a.size());
for (int i = l; i <= r; i++)
print(a[i], s);
print(e);
}
template<typename T>
void print(vector<T>& v, string s = " ", string e = "\n") {
for (int i = 0; i < v.size(); i++)
print(v[i], s);
print(e);
}
template<typename T>
void print(vector<T>& v, int n, string s = " ", string e = "\n") {
assert(0 <= n && n <= v.size());
for (int i = 0; i < n; i++)
print(v[i], s);
print(e);
}
template<typename T>
void print(vector<T>& v, int l, int r, string s = " ", string e = "\n") {
assert(0 <= l && l <= r && r < v.size());
for (int i = l; i <= r; i++)
print(v[i], s);
print(e);
}
template<typename T>
void print(ordered_set<T>& v, string s = " ", string e = "\n") {
for (auto x : v)
print(x, s);
print(e);
}
template<typename T>
void print(fast_set<T>& v, string s = " ", string e = "\n") {
for (auto x : v)
print(x, s);
print(e);
}
}
using namespace output;
namespace debugs {
// https://codeforces.com/blog/entry/91347
#define debug(...) logger(__PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string function, int line, string vars, Args&&... values) {
print(function, " - (line: ", line, "): {", vars, "} = {");
string delim = "";
(..., (print(delim, values), delim = ", "));
printl("}");
}
}
using namespace debugs;
}
using namespace dutinmeow;
//#define USACO 1
//#define FILEIO 1
#if !defined(USACO)
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#endif
// code
int N, M;
vector<int> adj[400005];
array<int, 400005> vis;
void dfs(int u, bool is_inf, fast_set<int> &s) {
if (s.find(u) != s.end())
is_inf = 1;
if (vis[u] != 0) {
if (is_inf) {
if (vis[u] == -1)
return;
vis[u] = -1;
}
else {
if (vis[u] == 2 || vis[u] == -1)
return;
vis[u] = 2;
}
}
else {
if (is_inf)
vis[u] = -1;
else
vis[u] = 1;
}
s.insert(u);
for (int v : adj[u])
dfs(v, is_inf, s);
//cout << u << " : " << is_inf << ',' << s << " : " << vis[u] << '\n';
s.erase(u);
}
void solve() {
read(N, M);
for (int i = 0; i < M; i++) {
int a, b;
read(a, b);
adj[a].PB(b);
}
fast_set<int> s;
dfs(1, 0, s);
for (int i = 1; i <= N; i++)
cout << vis[i] << ' ';
cout << '\n';
for (int i = 1; i <= N; i++) {
vis[i] = 0;
adj[i].clear();
}
}
signed main(void) {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef USACO
const string ___filename___ = "";
filein(___filename___ + ".in");
fileout(___filename___ + ".out");
#endif
#ifdef FILIO
filein("input.txt");
fileout("output.txt");
fileerr("error.txt");
#endif
int T = 1;
read(T);
for (int t = 1; t <= T; t++) {
// print("Case #", t, ": ");
solve();
}
} 语法
/*
* Created By: 'Present_Sir'
* Created On: Saturday 10 July 2021 09:06:11 PM
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
vector < vector < int > > gr(n);
for(int i=0; i<m; ++i){
int x, y;
cin >> x >> y;
--x; --y;
gr[x].push_back(y);
}
vector < int > vis(n, 0);
set < int > cur_parents;
set < int > parents;
function < void(int) > dfs = [&](int cur){
vis[cur]++;
cur_parents.insert(cur);
for(auto x: gr[cur]){
if(vis[x]){
if(cur_parents.find(x)!=cur_parents.end()){
parents.insert(x);
}else if(vis[x] == 1){
dfs(x);
}
}else{
dfs(x);
}
}
cur_parents.erase(cur);
return;
};
dfs(0);
vector < int > ans = vis;
function < void(int) > dfs2 = [&](int cur){
vis[cur] = 1;
ans[cur] = -1;
for(auto x: gr[cur]){
if(vis[x])continue;
dfs2(x);
}
return;
};
fill(vis.begin(), vis.end(), 0ll);
for(auto x: parents){
dfs2(x);
}
for(auto x: ans) cout << x << " ";
cout << "\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void solve() {
int n, m;
cin >> n >> m;
vector<vi> graph(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
graph[u].push_back(v);
}
vi res(n, 0);
// first do a dfs to find cycles.
vi in_stk(n, 0);
auto dfs_cyc = [&](auto self, int u) -> void {
assert(res[u] == 0);
res[u] = 1;
in_stk[u] = 1;
for (int v : graph[u]) {
if (in_stk[v]) {
res[u] = res[v] = -1;
} else if (res[v] == 0) {
self(self, v);
}
}
in_stk[u] = 0;
};
dfs_cyc(dfs_cyc, 0);
// mark everything reachable from a cycle
{
queue<int> q;
for (int u = 0; u < n; ++u) {
if (res[u] == -1) {
q.push(u);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
assert(res[u] == -1);
for (int v : graph[u]) {
if (res[v] != -1) {
res[v] = -1;
q.push(v);
}
}
}
}
// now handle multipaths
{
vi vis2(n, 0);
queue<int> q;
if (res[0] > 0) {
q.push(0);
vis2[0] = 1;
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (res[v] == -1) continue;
if (vis2[v] && res[v] == 1) {
res[v] = 2;
q.push(v);
} else if (!vis2[v]) {
vis2[v] = true;
res[v] = res[u];
q.push(v);
}
}
}
}
for (int i = 0; i < n; ++i) {
cout << res[i] << " \n"[i + 1 == n];
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int T;
cin >> T;
while (T-- > 0) {
solve();
}
return 0;
} 算法竞赛之路 文章被收录于专栏
整理、记录算法竞赛的好题
投递小鹏汽车等公司8个岗位
