Pagini recente » Cod sursa (job #884350) | Cod sursa (job #1848356) | Cod sursa (job #634812) | Cod sursa (job #987665) | Cod sursa (job #1232215)
#include <fstream>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;
ifstream is("ctc.in");
ofstream os("ctc.out");
int n, m, a, b;
int nrg; // nrg = indecs
vector<vector<int> > g, c; // g - vecini, c - ctc
vector<int> grup, gmin, con; // idx, lowlink
vector<bool> ok; // in_stack
stack<int> s;
void TARJAN(int nod);
int main()
{
is >> n >> m;
g.resize(n + 1);
for ( int i = 1; i <= m; ++i )
{
is >> a >> b;
g[a].push_back(b);
}
grup.resize(n + 1, INF);
gmin.resize(n + 1);
ok.resize(n + 1);
for ( int i = 1; i <= n; ++i )
{
if ( grup[i] == INF )
TARJAN(i);
}
os << c.size() << "\n";
for ( size_t i = 0; i < c.size(); ++i )
{
for ( size_t j = 0; j < c[i].size(); ++j )
os << c[i][j] << " ";
os << "\n";
}
is.close();
os.close();
return 0;
}
void TARJAN(int nod)
{
grup[nod] = gmin[nod] = nrg; // grup = idx, gmin = lowlink
++nrg;
s.push(nod);
ok[nod] = true;
for ( vector<int>::iterator it = g[nod].begin(); it != g[nod].end(); ++it )
{
if ( grup[*it] == INF )
{
TARJAN(*it);
gmin[nod] = min(gmin[nod], gmin[*it]);
}
else
if ( ok[*it] )
gmin[nod] = min(gmin[nod], gmin[*it]);
}
if ( grup[nod] == gmin[nod] )
{
con.clear();
int nod2;
do
{
con.push_back(nod2 = s.top());
s.pop();
ok[nod2] = false;
} while ( nod2 != nod );
c.push_back(con);
}
}