Pagini recente » Cod sursa (job #3213848) | Cod sursa (job #610629) | Cod sursa (job #24200) | Cod sursa (job #2224212) | Cod sursa (job #754126)
Cod sursa(job #754126)
#include <vector>
#include <fstream>
#include <stack>
#define FILEIN "ctc.in"
#define FILEOUT "ctc.out"
#define N 100010
using namespace std;
vector<vector<int> > graf;
vector<vector<int> > sol;
stack<int> S;
int n,m,timp;
int id[N];
int low[N];
bool exist[N];
void read()
{
graf.clear();
ifstream in(FILEIN);
in >> n >> m;
for (int i = 0; i <= n; i++)
graf.push_back(vector<int>());
for (int i = 0; i < m; i++)
{
int x,y;
in >> x >> y;
graf[x].push_back(y);
}
in.close();
}
void tdfs(int u)
{
id[u] = timp;
low[u] = timp++;
S.push(u);
exist[u] = true;
for (unsigned i = 0; i < graf[u].size(); i++)
{
int v = graf[u][i];
if (id[v] == -1)
{
tdfs(v);
if (low[v] < low[u])
low[u] = low[v];
continue;
}
if (exist[v] && low[v] < low[u])
low[u] = low[v];
}
if (low[u] == id[u])
{
sol.push_back(vector<int>());
do
{
int tmp = S.top();
S.pop();
exist[tmp] = false;
sol.back().push_back(tmp);
if (tmp == u)
break;
}
while (1);
}
}
void print()
{
ofstream out(FILEOUT);
int s = sol.size();
out << s << endl;
for (int i = 0; i < s; i++)
{
for (unsigned j = 0; j < sol[i].size(); j++)
out << sol[i][j] << " ";
out << endl;
}
out.close();
}
void tarjan()
{
for (int i = 1; i <= n; i++)
{
id[i] = -1;
exist[i] = false;
}
for (int i = 1; i <= n; i++)
if (id[i] == -1)
tdfs(i);
}
int main()
{
read();
tarjan();
print();
}