Pagini recente » Cod sursa (job #1398568) | Cod sursa (job #607831) | Cod sursa (job #2560740) | Cod sursa (job #1610056) | Cod sursa (job #1474498)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int Nmax = 100000;
int N,M,SCC = 0;
stack<int> KosarajuST;
vector<int> Comp[Nmax+1],Adj[Nmax+1],TAdj[Nmax+1];
bool seen[Nmax+1];
int comp[Nmax+1];
void Dfs1(int node)
{
seen[node] = 1;
for (vector<int>::iterator it = Adj[node].begin(); it != Adj[node].end(); ++it)
if (!seen[*it])
Dfs1(*it);
KosarajuST.push(node);
}
void Dfs2(int node)
{
comp[node] = SCC;
Comp[SCC].push_back(node);
for (vector<int>::iterator it = TAdj[node].begin(); it != TAdj[node].end(); ++it)
if (!comp[*it])
Dfs2(*it);
}
void Kosaraju()
{
for (int i = 1; i <= N; ++i)
if (!seen[i])
Dfs1(i);
while (!KosarajuST.empty())
{
if (!comp[KosarajuST.top()])
{
++SCC;
Dfs2(KosarajuST.top());
}
KosarajuST.pop();
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> N >> M;
for (int i = 1; i <= M; ++i)
{
int a,b;
fin >> a >> b;
Adj[a].push_back(b);
TAdj[b].push_back(a);
}
Kosaraju();
fout << SCC << "\n";
for (int i = 1; i <= SCC; ++i)
{
for (vector<int>::iterator it = Comp[i].begin(); it != Comp[i].end(); ++it)
fout << (*it) << " ";
fout << "\n";
}
}