Pagini recente » Cod sursa (job #1525327) | Cod sursa (job #424619) | Cod sursa (job #2245181) | Cod sursa (job #892838) | Cod sursa (job #2290896)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100001
using namespace std;
int N, M;
vector<int> G[MAXN];
vector<int> GT[MAXN];
vector<vector<int>> comps;
int comp_i=0;
int vis[MAXN];
stack<int> L;
void Read()
{
ifstream f("be.txt");
f>>N>>M;
for (int i=1;i<=N;i++)
{
G[i].push_back(0);
GT[i].push_back(0);
}
int a, b;
for (int i=0;i<M;i++)
{
f>>a>>b;
G[a].push_back(b);
GT[b].push_back(a);
G[a][0]++;
GT[b][0]++;
}
}
void Visit(int a)
{
if (vis[a])
return;
vis[a]=-1;
for (int i=1;i<=G[a][0];i++)
if (!vis[G[a][i]])
Visit(G[a][i]);
L.push(a);
}
void Assign(int a, int root)
{
if (vis[a]!=-1)
return;
vis[a]=root;
comps[comp_i].push_back(a);
for (int i=1;i<=GT[a][0];i++)
Assign(GT[a][i], root);
}
void Kosaraju()
{
for (int i=1;i<=N;i++)
if (!vis[i])
Visit(i);
int b;
while(!L.empty())
{
b=L.top();
if (vis[b]==-1)
{
vector<int> tmp;
comps.push_back(tmp);
Assign(b, b);
comp_i++;
}
L.pop();
}
//for (int i=1;i<=N;i++)
// cout<<vis[i]<<' ';
}
void Write()
{
ofstream g("ki.txt");
g<<comps.size()<<'\n';
for (int i=0;i<comps.size();i++)
{
for (int j=0;j<comps[i].size();j++)
g<<comps[i][j]<<' ';
g<<'\n';
}
}
int main()
{
Read();
Kosaraju();
Write();
}