Pagini recente » Cod sursa (job #1485686) | Cod sursa (job #2094656) | Cod sursa (job #476832)
Cod sursa(job #476832)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
int N, M, K;
vector< vector<int> > Deg;
vector< set<int> > Com;
vector<int> Dfn, Low;
vector<bool> InS;
stack<int> Stk;
void read()
{
int x, y;
ifstream fin("ctc.in");
fin >> N >> M;
Deg.assign(N + 1, vector<int>());
while (M--)
{
fin >> x >> y;
Deg[x].push_back(y);
}
fin.close();
}
void tarjan(int u)
{
int v;
Low[u] = Dfn[u] = ++K;
Stk.push(u);
InS[u] = true;
for (vector<int>::iterator i = Deg[u].begin(); i != Deg[u].end(); ++i)
{
v = *i;
if (Dfn[v] == 0)
{
tarjan(v);
Low[u] = min(Low[u], Low[v]);
}
else if(InS[v])
{
Low[u] = min(Low[u], Dfn[v]);
}
}
if (Low[u] == Dfn[u])
{
Com.push_back(set<int>());
do
{
v = Stk.top();
Stk.pop();
InS[v] = false;
Com[Com.size() - 1].insert(v);
}
while(v != u);
}
}
void solve()
{
Low.assign(N + 1, 0);
Dfn.assign(N + 1, 0);
InS.assign(N + 1, false);
for (int i = 1; i <= N; ++i)
{
if (Dfn[i] == 0)
{
tarjan(i);
}
}
}
void write()
{
ofstream fout("ctc.out");
fout << Com.size() << '\n';
for (vector< set<int> >::iterator i = Com.begin(); i != Com.end(); ++i)
{
for (set<int>::iterator j = i->begin(); j != i->end(); ++j)
{
fout << *j << ' ';
}
fout << '\n';
}
fout.close();
}
int main()
{
read();
solve();
write();
return 0;
}