Pagini recente » Cod sursa (job #2068630) | Cod sursa (job #1959925) | Cod sursa (job #771451) | Cod sursa (job #1298649) | Cod sursa (job #2029425)
#include <bits/stdc++.h>
using namespace std;
vector <int> graf[100005];
vector <int> igraf[100005];
vector <int> ctc[100005];
vector <int> compgraf[100005];
int in[100005];
int where[100005];
map <pair<int, int>, int> dist;
int cate;
int viz[100005];
queue <int> Q;
vector <int> v;
void bkt (int node, int lvl, int C, int start)
{
if (dist.count({start, node}) == 0)
{
dist[{start, node}] = lvl;
}
else
{
int maxim = max(dist[{start, node}], lvl);
dist[{start, node}] = maxim;
}
for (auto x:graf[node])
{
if (where[x] != where[node]) continue;
if (viz[x]) continue;
viz[x] = 1;
bkt (x, lvl+1, C, start);
viz[x] = 0;
}
}
int dp[100005];
int dp_vechi[100005];
void dfs1 (int node)
{
viz[node] = 1;
for (auto x:graf[node])
{
if (viz[node]) continue;
dfs1(x);
}
v.push_back(node);
}
void dfs2 (int node, int C)
{
viz[node] = 0;
where[node] = C;
ctc[C].push_back(node);
for (auto x:graf[node])
{
if (!viz[x]) continue;
dfs2(x, C);
}
}
int main(){
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 1; i<=m; ++i)
{
int x, y;
cin >> x >> y;
graf[x].push_back(y);
igraf[y].push_back(x);
}
for (int i = 1; i<=n; ++i)
{
if (viz[i] == 0)
dfs1(i);
}
reverse(v.begin(), v.end());
for (auto x:v)
{
if (viz[x])
{
++cate;
dfs2(x, cate);
}
}
cout << cate << '\n';
for (int i = 1; i<=cate; ++i)
{
for (auto x:ctc[i])
cout << x << ' ';
cout << '\n';
}
return 0;
for (int i = 1; i<=cate; ++i)
{
// assert (ctc[i].size() <= 7);
for (auto j:ctc[i])
{
viz[j] = 1;
bkt(j, 0, i, j);
viz[j] = 0;
}
}
for (int i = 1; i<=n; ++i)
{
int wi = where[i];
for (auto x:graf[i])
{
int wx = where[x];
if (wx == wi) continue;
in[wx]++;
}
}
for (int i = 1; i<=cate; ++i)
{
if (in[i] == 0)
{
Q.push(i);
}
}
while (Q.empty() == 0)
{
int CC = Q.front();
Q.pop();
for (auto x:ctc[CC])
dp_vechi[x] = dp[x];
for (auto x:ctc[CC])
{
for (auto y:ctc[CC])
{
dp[y] = max(dp_vechi[x] + dist[{x, y}], dp[y]);
}
}
for (auto x:ctc[CC])
{
for (auto y:graf[x])
{
if (where[y] == CC) continue;
dp[y] = max(dp[y], dp[x]+1);
in[where[y]]--;
if (in[where[y]] == 0) Q.push(where[y]);
}
}
}
int maxim = 0;
for (int i = 1; i<=n; ++i)
{
maxim = max(maxim, dp[i]);
}
cout << maxim+1;
return 0;
}