Pagini recente » Cod sursa (job #585459) | Cod sursa (job #621596) | Cod sursa (job #2116322) | Cod sursa (job #316578) | Cod sursa (job #2871157)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
const int N_MAX = 100001;
int n, m, scc;
bool visited[N_MAX];
vector <int> G1[N_MAX], G2[N_MAX], SCC[N_MAX];
stack <int> S;
void Read()
{
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
G1[x].push_back(y);
G2[y].push_back(x);
}
}
void DFS1(int start)
{
visited[start] = true;
for (unsigned int i = 0; i < G1[start].size(); i++)
{
int neighbour = G1[start][i];
if (visited[neighbour] == false)
{
DFS1(neighbour);
}
}
S.push(start);
}
void DFS2(int start)
{
SCC[scc].push_back(start);
visited[start] = false;
for (unsigned int i = 0; i < G2[start].size(); i++)
{
int neighbour = G2[start][i];
if (visited[neighbour] == true)
{
DFS2(neighbour);
}
}
}
int main()
{
Read();
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();
}
g << scc << "\n";
for (int i = 1; i <= scc; i++)
{
for (unsigned int j = 0; j < SCC[i].size(); j++)
{
g << SCC[i][j] << " ";
}
g << "\n";
}
}