Pagini recente » Cod sursa (job #734873) | Cod sursa (job #2102677) | Cod sursa (job #1306615) | Cod sursa (job #2636751) | Cod sursa (job #2982800)
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int N = 100000;
string file = "ctc";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
vector <int> succesori[N + 1], predecesori[N + 1], sir;
vector <vector <int> > conexe;
bitset<N + 1>viz;
void dfs(int x)
{
viz[x] = 1;
for (int y : succesori[x])
{
if (!viz[y])
{
dfs(y);
}
}
sir.push_back(x);
}
void dfs_t(int x)
{
viz[x] = 0;
conexe[conexe.size() - 1].push_back(x);
for (int y : predecesori[x])
{
if (viz[y])
{
dfs_t(y);
}
}
}
int main()
{
int n, m, x, y;
cin >> n >> m;
while (m)
{
m--;
cin >> x >> y;
succesori[x].push_back(y);
predecesori[y].push_back(x);
}
for (int i = 1; i <= n; i++)
{
if (!viz[i])
{
dfs(i);
}
}
reverse(sir.begin(), sir.end());
for (int x : sir)
{
if (viz[x])
{
vector <int> comp;
conexe.push_back(comp);
dfs_t(x);
}
}
cout << conexe.size() << '\n';
for (int i = 0; i < conexe.size(); i++)
{
for (int j : conexe[i])
{
cout << j << ' ';
}
cout << endl;
}
}