Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <bitset>
- #include <queue>
- #include <cstring>
- using namespace std;
- class InputReader
- {
- public:
- static const int BUFF_SIZE = 1 << 17;
- FILE *fin;
- int bp;
- char buff[BUFF_SIZE];
- InputReader (const char *file_name)
- {
- fin = fopen(file_name, "r");
- bp = BUFF_SIZE - 1;
- }
- void adv()
- {
- if (++bp == BUFF_SIZE)
- {
- fread(buff, sizeof(char), BUFF_SIZE, fin);
- bp = 0;
- }
- }
- InputReader& operator >> (int& num)
- {
- num = 0;
- while (isdigit(buff[bp]) == false)
- adv();
- while (isdigit(buff[bp]))
- {
- num = num * 10 + buff[bp] - '0';
- adv();
- }
- return *this;
- }
- };
- InputReader fin("feisbuc.in");
- ofstream fout("feisbuc.out");
- const int MAXN = 5005;
- int maxim, minim = 0;
- int r[MAXN], aux[MAXN], z = 0;
- bitset < MAXN > viz;
- vector < int > v[MAXN];
- int minval[MAXN], cnt;
- void dfs(int nod)
- {
- viz[nod] = 1;
- for (auto &it : v[nod])
- {
- if (!viz[it])
- {
- r[it] = cnt;
- dfs(it);
- }
- }
- }
- queue < int > Q;
- int dist[MAXN];
- int ok;
- void bfs()
- {
- int nod;
- while (!Q.empty())
- {
- nod = Q.front();
- Q.pop();
- for (auto &it : v[nod])
- {
- if (dist[it] == -1)
- {
- Q.push(it);
- dist[it] = dist[nod] + 1;
- aux[++z] = it;
- if (dist[it] > minval[r[it]])
- {
- ok = 0;
- while (!Q.empty()) Q.pop();
- return;
- }
- }
- }
- }
- }
- int main()
- {
- int n, m, i, x, y, j;
- memset(minval, 1000000, sizeof minval);
- memset(dist, -1, sizeof dist);
- fin >> n >> m;
- for (i = 1; i <= m; ++i)
- {
- fin >> x >> y;
- v[x].push_back(y);
- v[y].push_back(x);
- }
- for (i = 1; i <= n; ++i)
- {
- if (!viz[i])
- {
- ++cnt;
- r[i] = cnt;
- dfs(i);
- }
- }
- for (i = 1; i <= n; ++i)
- {
- ok = 1;
- Q.push(i);
- maxim = 0;
- dist[i] = 0;
- aux[++z] = i;
- bfs();
- if (!ok)
- {
- for (j = 1; j <= z; ++j)
- {
- dist[aux[j]] = -1;
- }
- z = 0;
- continue;
- }
- for (j = 1; j <= z; ++j)
- {
- if (dist[aux[j]] > maxim) maxim = dist[aux[j]];
- dist[aux[j]] = -1;
- }
- if (minval[r[i]] > maxim) minval[r[i]] = maxim;
- z = 0;
- }
- for (i = 1; i <= cnt; ++i)
- {
- if (minval[r[i]] > minim) minim = minval[r[i]];
- }
- fout << cnt << ' ' << ++minim << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement