Pagini recente » Cod sursa (job #2206463) | Cod sursa (job #2714584) | Cod sursa (job #1064096) | Cod sursa (job #421972) | Cod sursa (job #2764548)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int n, m, scc, visited[100001];
vector <int> G[100001], GT[100001], SCC[100001];
stack <int> S;
void Read()
{
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void Print()
{
g << scc << endl;
for (int i = 1; i <= scc; i++)
{
for (int j = 0; j < SCC[i].size(); j++)
{
g << SCC[i][j] << " ";
}
g << endl;
}
}
void DFS1(int at)
{
visited[at] = 1;
for (int i = 0; i < G[at].size(); i++)
{
int to = G[at][i];
if (visited[to] == 0)
{
DFS1(to);
}
}
S.push(at);
}
void DFS2(int at)
{
visited[at] = 2;
SCC[scc].push_back(at);
for (int i = 0; i < GT[at].size(); i++)
{
int to = GT[at][i];
if (visited[to] == 1)
{
DFS2(to);
}
}
}
void Solve()
{
for (int i = 1; i <= n; i++)
{
if (visited[i] == 0)
{
DFS1(i);
}
}
while (S.empty() == false)
{
int node = S.top();
if (visited[node] == 1)
{
scc++;
DFS2(node);
}
S.pop();
}
}
int main()
{
Read();
Solve();
Print();
}