Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 700 + 9;
- vector <int> adj[N];
- int n, m, meh[N], colored[N];
- char can[N][N];
- int Try (int column) {
- if (column > n)
- return 0;
- int res = 0;
- for (int i = 1; i <= n; i++) {
- if (colored[i])
- continue;
- if (can[i][column] == '0')
- continue;
- if (!meh[i])
- continue;
- res++;
- colored[i] = true;
- for (auto u: adj[i])
- meh[u] = true;
- }
- return res + Try (column + 1);
- }
- void solve () {
- cin >> n >> m;
- for (int i = 1; i <= m; i++) {
- int u, v;
- cin >> u >> v;
- adj[u].push_back (v);
- adj[v].push_back (u);
- }
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- cin >> can[i][j];
- int res = -1, loly = 0;
- for (int firstNode = 1; firstNode <= n; firstNode++) {
- for (int delay = 1; delay <= n; delay++) {
- if (can[firstNode][delay] == '0')
- continue;
- memset (meh, 0, sizeof (meh));
- memset (colored, 0, sizeof (colored));
- meh[firstNode] = colored[firstNode] = true;
- for (auto u: adj[firstNode])
- meh[u] = true;
- int newRes = (1 + Try (delay + 1));
- if (newRes >= res) {
- res = newRes;
- loly = delay;
- }
- //res = max (res, 1 + Try (delay + 1));
- }
- }
- for (int i = 1; i <= n; i++)
- adj[i].clear();
- cout << res;
- if (res == -1)
- cout << "\n";
- else {
- cout << " " << loly << "\n";
- }
- return;
- }
- int main () {
- int t = 1;
- cin >> t;
- while (t--)
- solve ();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement