Pagini recente » Cod sursa (job #867115) | Cod sursa (job #1794813) | Cod sursa (job #2731261) | Cod sursa (job #1134599) | Cod sursa (job #2764562)
#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 <vector <int>> V1, V2, SCC;
stack <int> S;
void Read()
{
f >> n >> m;
V1 = V2 = SCC = vector <vector <int>> (n + 1);
for (int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
V1[x].push_back(y);
V2[y].push_back(x);
}
}
void Print()
{
g << scc << "\n";
for (int i = 1; i <= scc; i++)
{
for (int j = 0; j < SCC[i].size(); j++)
{
g << SCC[i][j] << " ";
}
g << "\n";
}
}
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;
SCC[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 node = S.top();
if (visited[node] == true)
{
scc++;
DFS2(node);
}
S.pop();
}
}
int main()
{
Read();
Solve();
Print();
}