Pagini recente » Cod sursa (job #3151213) | Cod sursa (job #3216094) | Cod sursa (job #270978) | Cod sursa (job #2315574) | Cod sursa (job #2668100)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
stack<int> stiva;
vector<int> result[10000000];
int culoare;
void DFS(int node, vector<int> &visited, vector<int> fii[])
{
visited[node] = true;
for (int i = 0; i < fii[node].size(); ++i)
if (visited[fii[node][i]] == 0)
DFS(fii[node][i], visited, fii);
stiva.push(node);
}
void DFS2(int node, vector<int> &visited, vector<int> parinti[])
{
visited[node] = true;
result[culoare].push_back(node);
for (int i = 0; i < parinti[node].size(); ++i)
if (visited[parinti[node][i]] == false)
DFS2(parinti[node][i], visited, parinti);
}
int main()
{
int n, m;
fin >> n >> m;
vector<int> fii[n + 1];
vector<int> parinti[n + 1];
for (int i = 0; i < m; ++i)
{
int x, y;
fin >> x >> y;
fii[x].push_back(y);
parinti[y].push_back(x);
}
vector<int> visited(n + 1);
for (int i = 1; i <= n; ++i)
if (visited[i] == 0)
DFS(i, visited, fii);
for (int i = 1; i <= n; ++i)
visited[i] = 0;
while (!stiva.empty())
{
int node = stiva.top();
if (visited[node] == false)
{
culoare++;
DFS2(node, visited, parinti);
}
stiva.pop();
}
fout << culoare << '\n';
for (int i = 1; i <= culoare; ++i)
{
for (int j = 0; j < result[i].size(); j++)
fout << result[i][j] << " ";
fout << endl;
}
fin.close();
fout.close();
return 0;
}