Pagini recente » Cod sursa (job #540949) | Cod sursa (job #2080251) | Cod sursa (job #450079) | Cod sursa (job #2823495) | Cod sursa (job #2764485)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int n, m, scc;
bool visited[100001];
vector <int> V1[100001], V2[100001], vec[100001];
stack <int> S;
void Read()
{
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
V1[x].push_back(y);
V2[y].push_back(x);
}
}
void DFS1(int at)
{
visited[at] = true;
for (int i = 0; i < V1[at].size(); i++)
{
int to = V1[at][i];
if (visited[to] == false)
{
DFS1(to);
}
}
S.push(at);
}
void DFS2(int at)
{
visited[at] = false;
vec[scc].push_back(at);
for (int i = 0; i < V2[at].size(); i++)
{
int to = V2[at][i];
if (visited[to] == true)
{
DFS2(to);
}
}
}
void Solve()
{
for (int i = 1; i <= n; i++)
{
if (visited[i] == false)
{
DFS1(i);
}
}
while (S.empty() == false)
{
int at = S.top();
if (visited[at] == true)
{
scc++;
DFS2(at);
}
S.pop();
}
}
void Print()
{
g << scc << endl;
for (int i = 1; i <= scc; i++)
{
for (int j = 0; j < vec[i].size(); j++)
{
g << vec[i][j] << " ";
}
g << endl;
}
}
int main()
{
Read();
Solve();
Print();
return 0;
}