AcWing 4793. 危险程度
原题链接
困难
作者:
Coinisi.
,
2023-01-07 20:16:30
,
所有人可见
,
阅读 187
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
#define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }
const int N = 5e5+10, mod = 1e9+7, M = 1e6+5, K = 1e5+10, Z = 2e5+7;
using namespace std;
typedef long long LL;
typedef priority_queue<int> PQI;
typedef priority_queue <int, vector<int>, greater<>> PQGI;
typedef pair<int, int> PII;
bool g[130][130];// 存能不能发生反应
bool st[130][130], flag[51];// flag防止已经进去的物质再次计算发生反应
queue<int> s;
void solve()
{
int n, m, danger = 1; cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
int x, y; cin >> x >> y;
g[x][y] = g[y][x] = true;
} // 存入每一个能发生反应的两种化学物质
s.push(1);flag[1] = true;
for(int i = s.front(); i <= n; i = s.front()) // 模拟bfs进行广搜
{
s.pop();
for(int j = 1; j <= n; j ++)
if(g[i][j] == true && st[i][j] == false && flag[j] == false)
{
s.push(j);
danger = danger * 2, st[i][j] = st[j][i] = true, flag[j] = true;
} // flag防止已经进去的物质再次计算发生反应
if(!s.size()) // 如果没有可以发生反应的任意寻找一个还没反应的物质开始遍历
for(int k = 1; k <= n; k ++)
if(flag[k] == false)
{
flag[k] = true;
s.push(k);
break;
}
if(!s.size()) break; // 如果搜完还是空的说明,n个物质已经全部进入试管
}
cout << danger << endl;
}
signed main()
{
IOS; cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while( T -- ) solve();
return 0;
}