Pagini recente » Cod sursa (job #983452) | Cod sursa (job #887152) | Cod sursa (job #2851761) | Cod sursa (job #3232334) | Cod sursa (job #3261804)
#include <deque>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iostream>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <bitset>
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;
typedef pair<int, int> pi;
void DFS(int nod, vector<vector<int>>& edges, vector<int>& vis, vector<int>& timeOut, int& timeElaps) {
timeElaps += 1;
vis[nod] = 1;
for (int x : edges[nod]) {
if (!vis[x]) {
DFS(x, edges, vis, timeOut, timeElaps);
}
}
timeElaps += 1;
vis[nod] = 2;
timeOut[nod] = timeElaps;
}
void DFST(int nod, vector<vector<int>>& edges, vector<int>& vis, vector<int>& comp) {
comp.push_back(nod);
vis[nod] = 1;
for (int x : edges[nod]) {
if (!vis[x]) {
DFST(x, edges, vis, comp);
}
}
vis[nod] = 2;
}
int getMaxVisitableWebpages() {
int N, M;
f >> N >> M;
vector<vector<int>> V(N);
vector<vector<int>> VT(N);
for (int i = 0; i < M; i++) {
int a, b;
f >> a >> b;
a--;
b--;
V[a].push_back(b);
VT[b].push_back(a);
}
int timeElaps = 0;
vector<int> vis(N, 0), timeOut(N, 0);
for (int i = 0; i < N; i++) {
if (!vis[i]) {
DFS(i, V, vis, timeOut, timeElaps);
}
}
vector<pi> topOrder;
for (int i = 0; i < N; i++) {
topOrder.push_back({ i, timeOut[i] });
//cout << i << ' ' << timeOut[i] << '\n';
vis[i] = 0;
}
sort(topOrder.begin(), topOrder.end(), [&](const pi& X, const pi& Y) {
return X.second <= Y.second;
});
topOrder.resize(topOrder.size());
vector<vector<int>> ans;
for (int i = N - 1; i >= 0; i--) {
if (!vis[topOrder[i].first]) {
vector<int> comp;
DFST(topOrder[i].first, VT, vis, comp);
ans.push_back(comp);
}
}
g << ans.size() << '\n';
for (vector<int>& comp : ans) {
for (int el : comp) {
g << el + 1 << ' ';
}
g << '\n';
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
getMaxVisitableWebpages();
return 0;
}