This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10;
const int INF = 0x3f3f3f3f;
set<pair<int, int> > verts;
array<set<int>, MAXN> grafo;
vector<int> active;
int grau[MAXN];
int resp = 0;
void bt(set<int>::iterator it, int v)
{
if (it == grafo[v].end())
{
resp = max(resp, (int)active.size()+1);
return;
}
// cerr << *it << '\n';
auto aux = it;
bt(++aux, v);
for (auto viz : active) if (grafo[*it].find(viz) == grafo[*it].end()) return;
active.push_back(*it);
aux = it;
bt(++aux, v);
active.pop_back();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
for (int i = 0; i < N; i++)
{
cin >> grau[i];
for (int j = 0; j < grau[i]; j++)
{
int X;
cin >> X;
grafo[i].insert(X);
}
verts.emplace(grau[i], i);
}
while (!verts.empty())
{
// for (auto [g, id] : verts) cerr << "||" << g << " " << id << " ";
// cerr << '\n';
int cur = verts.begin()->second; verts.erase(verts.begin());
bt(grafo[cur].begin(), cur);
for (auto viz : grafo[cur])
{
grafo[viz].erase(cur);
verts.erase(make_pair(grau[viz], viz));
grau[viz]--;
verts.emplace(grau[viz], viz);
}
grafo[cur].clear(); grau[cur] = INF;
}
cout << resp << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |