Pagini recente » Cod sursa (job #839014) | Cod sursa (job #269348) | Cod sursa (job #2174058) | Cod sursa (job #3217930) | Cod sursa (job #2927378)
#include <fstream>
#include <vector>
#include <string>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, c = 0;
vector<bool> vis, vis_tr;
vector< vector<int> > adj, adj_tr;
vector<string> out;
stack<int> s;
void dfs_order(int v)
{
vis[v] = true;
for (int i = 0; i < adj[v].size(); i++)
{
if (!vis[adj[v][i]])
{
dfs_order(adj[v][i]);
}
}
s.push(v);
}
void dfs(int v)
{
vis_tr[v] = true;
out[c] += to_string(v) + ' ';
for (int i = 0; i < adj_tr[v].size(); i++)
{
if (!vis_tr[adj_tr[v][i]])
{
dfs(adj_tr[v][i]);
}
}
}
int main()
{
fin >> n >> m;
adj.resize(n + 1);
adj_tr.resize(n + 1);
for (int i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
adj[x].push_back(y);
adj_tr[y].push_back(x);
}
vis.resize(n + 1, false);
vis_tr.resize(n + 1, false);
for (int v = 1; v <= n; v++)
{
if (!vis[v])
{
dfs_order(v);
}
}
while (!s.empty())
{
int v = s.top();
s.pop();
if (!vis_tr[v])
{
out.push_back("");
dfs(v);
c++;
}
}
fout << c << '\n';
for (int i = 0; i < c; i++)
{
fout << out[i] << '\n';
}
}