Pagini recente » Cod sursa (job #1610821) | Cod sursa (job #1050312) | Cod sursa (job #1848707) | Cod sursa (job #2223293) | Cod sursa (job #2925804)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>
using namespace std;
const int N = 1e5 + 1;
vector <int> L[N], T[N];
vector <vector<int>> scc;
bitset <N> vis;
stack<int> found;
int n;
void Read()
{
ifstream fin ("ctc.in");
int m, x , y;
fin >> n >> m;
while (m--)
{
fin >> x >> y;
L[x].push_back(y);
T[y].push_back(x);
}
fin.close();
}
void First_DFS(int vertex)
{
vis[vertex] = 1;
for (auto& next : L[vertex])
if (!vis[next])
First_DFS(next);
found.push(vertex);
}
void Second_DFS(int vertex)
{
vis[vertex] = 0;
scc[scc.size() - 1].push_back(vertex);
for (auto& next : T[vertex])
if (vis[next])
Second_DFS(next);
}
void Kosaraju()
{
for (int i = 1; i <= n; i++)
if(!vis[i])
First_DFS(i);
while (!found.empty())
{
int vertex = found.top();
found.pop();
cout << vertex << " ";
if (vis[vertex])
{
scc.push_back({});
Second_DFS(vertex);
}
}
}
void Write()
{
ofstream fout ("ctc.out");
fout << scc.size() << "\n";
for (int i = 0; i < scc.size(); i++, fout << "\n")
for (int j = 0; j < scc[i].size(); j++)
fout << scc[i][j] << " ";
fout.close();
}
int main(){
Read();
Kosaraju();
Write();
return 0;
}